257. 二叉树的所有路径

2020-03-10  本文已影响0人  lazy_ccccat

题目描述

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);
    }
};
上一篇 下一篇

猜你喜欢

热点阅读