257. 二叉树的所有路径

力扣链接(简单)：https://leetcode.cn/problems/binary-tree-paths

有时感觉力扣也挺沙壁的，很多题并不简单，却标简单；反观一些中等题却蠢得要命。

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

个人题解

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& result) {
        // 每条路径都是从根节点开始的，所以先加入path
        // 这里不用判空，因为调用 traversal 前会检查
        path.push_back(node->val);

        // 遇到叶子节点, 把整个路径加入结果
        if(!node->left && !node->right) {
            int cnt = 0;
            string _path;
            for(auto _node:path) {
                cnt++;
                _path += to_string(_node);
                if(cnt < path.size()) _path += "->";
            }
            // 一条路径完成，退出函数
            result.push_back(_path);
            return;
        }

        // 非叶子节点，则继续递归子节点
        // 「关于 path.pop_back() 为何放在 traversal之后？」
        // 递归终止条件即为遇到叶子节点，所以 traversal 递归完成返回的时候一定是遍历到了叶子节点
        // 所以此时需要回溯到上一个节点，继续遍历右子树
        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<int> path;
        vector<string> result;

        if(!root) return result;

        traversal(root, path, result);
        return result;
    }
};

迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        // 遍历节点
        stack<TreeNode*> treeSt;
        // 遍历路径
        stack<string> pathSt;
        vector<string> result;

        if(!root) return result;
        // 将根节点加入栈并加入路径
        treeSt.push(root);
        pathSt.push(to_string(root->val));

        while(!treeSt.empty()) {
            // 首先把根节点搞进去
            auto node = treeSt.top(); treeSt.pop();
            // 每轮循环都会按照出栈顺序对 path 进行迭代，如遇到叶子节点，则 path 迭代完成
            string path = pathSt.top(); pathSt.pop();

            // 是叶子节点，path 迭代完成
            if(!node->left && !node->right) {
                result.push_back(path);
            }

            // 右子树
            if(node->right) {
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            // 左子树
            if(node->left) {
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }

        return result;
    }
};