257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

题解

思路：该题求根节点到叶子节点的路径，所以采用前序遍历(父节点指向孩子节点)。这题涉及到回溯。前序遍历及其回溯过程如下：

方法一：递归

代码(C++)

//递归：前序遍历
class Solution {
public:
    void traversal(TreeNode* node, vector<int> &path, vector<string> &result){
        path.push_back(node->val);//中
        if (node->left == nullptr && node->right == nullptr) {
            string spath = "";
            for(int i = 0; i < path.size() - 1; i++) {
                spath += to_string(path[i]) + "->";
            }
            spath += to_string(path[path.size() - 1]);
            result.push_back(spath);
            return;
        }
        if (node->left) { //左
            traversal(node->left, path, result);
            path.pop_back(); //回溯
        }
        if (node->right) { //右
            traversal(node->right, path, result);
            path.pop_back(); //回溯
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == nullptr) return result;
        traversal(root, path, result);
        return result;
    }
};

代码(JavaScript)

//递归：前序遍历
function getPath(node, path, result) {
    path.push(node.val); //中
    if (node.left === null && node.right === null) {
        var spath = "";
        for (var i = 0; i < path.length - 1; i++) {
            spath += path[i] + "->";
        }
        spath += path[path.length - 1];
        result.push(spath);
        return;
    }
    if (node.left) { //左
        getPath(node.left, path, result);
        path.pop(); //回溯
    }
    if (node.right) { //右
        getPath(node.right, path, result);
        path.pop(); //回溯
    }
}

var binaryTreePaths = function(root) {
    let result = [];
    let path = [];
    if (root == null) return result;
    getPath(root, path, result);
    return result;
};

方法二：迭代

代码(C++)

//迭代：前序遍历
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result; //最终的路径集合
        stack<TreeNode*> treeSt; //存放遍历的节点的栈
        stack<string> pathSt; //存放临时路径的栈
        if (root == nullptr) return result;
        else {
            treeSt.push(root);
            pathSt.push(to_string(root->val));
        }
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top();
            if (node != nullptr) {
                string spath = pathSt.top();
                treeSt.pop();
                pathSt.pop();
                if (node->right == nullptr && node->left == nullptr) {
                    result.push_back(spath);
                }
                if (node->right) {//右
                    treeSt.push(node->right);
                    pathSt.push(spath + "->" + to_string(node->right->val));
                }
                if (node->left) {//左
                    treeSt.push(node->left);
                    pathSt.push(spath + "->" + to_string(node->left->val));
                }
                treeSt.push(node); //中
                treeSt.push(nullptr); //null
            } else {
                treeSt.pop();
                treeSt.pop();
            }
        }
        return result;
    }
};

代码(JavaScript)

//迭代:统一前序遍历(右左中null)
var binaryTreePaths = function(root) {
    let pathSt = []; //存放临时路径的栈
    let treeSt = []; //存放遍历的节点的栈
    let result = []; //最终的路径集合
    if (root === null) return result;
    else {
        treeSt.push(root);
        pathSt.push(root.val + ""); // + "" 是让root.val 转成 字符串
    }
    while (treeSt.length != 0) {
        var node = treeSt.pop();
        if (node != null) {
            var spath = pathSt.pop();
            if (node.left === null && node.right === null) {
                result.push(spath);
            }
            if (node.right) { //右
                treeSt.push(node.right);
                pathSt.push(spath + "->" + node.right.val);
            }
            if (node.left) { //左
                treeSt.push(node.left);
                pathSt.push(spath + "->" + node.left.val);
            }
            treeSt.push(node); //中
            treeSt.push(null); //null
        } else {
            treeSt.pop();
        }
    }
    return result;
};