美文网首页
257. 二叉树的所有路径

257. 二叉树的所有路径

作者: lazy_ccccat | 来源:发表于2020-03-10 21:17 被阅读0次

    题目描述

    https://leetcode-cn.com/problems/binary-tree-paths/

    思路

    回溯第一题~~~~
    果然脑子转不过弯,但是呢呢给讲了下我立马就明白了,在这记录下。
    回溯和递归的区别,就是回溯需要修改状态,因此需要恢复现场,而递归不一定。具体说明:
    题目中给的二叉树的例子,从1出发找路径,可以去左孩子2,也可以去右孩子3。
    往左孩子探的话,路径字符串 1->2。往右孩子探的话,路径字符串1->3.
    你探完左孩子,再回到1(回溯),去探右孩子之前,路径字符串必须由1->2再恢复成1(恢复现场),再去探右孩子.
    不然探右孩子的时候,路径字符串就变成了1->2->3.
    明白了就好写了。
    但是这个题,路径字符串可以直接用string,而不是string &,这样就省得回溯回去的时候恢复这个路径字符串了。
    然后结合代码,好好体会下就算入门了。
    以后要做的八皇后问题也是这样,往下走每一步都有8个选择,每个选择探完回到原点都要恢复现场,再去探下一个选择。

    代码

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> paths;
            if (root) findPath(root, paths, "");
            return paths;
        }
    
        void findPath(TreeNode* root, vector<string>& paths, string s) {
            if (!root->left && !root->right) paths.push_back(s+to_string(root->val));
            if (root->left) findPath(root->left, paths, s + to_string(root->val) + "->");
            if (root->right) findPath(root->right, paths, s + to_string(root->val) + "->");
        }
    };
    

    follow up

    113. 路径总和 II

    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> res;
            vector<int> one;
            if (!root) return res;
            dfs(root, sum, one, res);
            return res;
        }
    
        void dfs(TreeNode* root, int sum, vector<int> one, vector<vector<int>>& res) {
            one.push_back(root->val);
            if (!root->left && !root->right) {
                if (sum == root->val) {
                    res.push_back(one);
                }
            }
            if (root->left) dfs(root->left, sum - root->val, one, res);
            if (root->right) dfs(root->right, sum - root->val, one, res);
        }
    };
    

    相关文章

      网友评论

          本文标题:257. 二叉树的所有路径

          本文链接:https://www.haomeiwen.com/subject/dwxndhtx.html