美文网首页
二叉树的路径和

二叉树的路径和

作者: Magic11 | 来源:发表于2019-03-20 10:33 被阅读0次

    1、二叉树的路径和
    https://www.lintcode.com/problem/binary-tree-path-sum/description
    描述
    给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。

    一个有效的路径,指的是从根节点到叶节点的路径。
    您在真实的面试中是否遇到过这个题? 是
    题目纠错
    样例
    输入:
    {1,2,4,2,3}
    5
    输出: [[1, 2, 2],[1, 4]]
    说明:
    这棵树如下图所示:
    1
    /
    2 4
    /
    2 3
    对于目标总和为5,很显然1 + 2 + 2 = 1 + 4 = 5

    class Solution {
    public:
        /*
         * @param root: the root of binary tree
         * @param target: An integer
         * @return: all valid paths
         */
        vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
            // write your code here
            vector<vector<int>> vecRes;
            vector<int> vec;
            pathSum(vecRes, vec, root, target);
            return vecRes;
        }
        
        void pathSum(vector<vector<int>> &vecRes, vector<int> &vec, TreeNode * node, int target) {
            if (NULL == node) {
                return;
            }
            vec.push_back(node->val);
            if (NULL == node->left && NULL == node->right) {
                int sum = accumulate(vec.begin(), vec.end(), 0);
                if (sum == target) {
                    vector<int> newVec(vec);
                    vecRes.push_back(newVec);
                }
            }
            
            
            if (NULL != node->left) {
                pathSum(vecRes, vec, node->left, target);
                vec.pop_back();
            }
            
            if (NULL != node->right) {
                pathSum(vecRes, vec, node->right, target);
                vec.pop_back();
            }
        }
    };
    

    2、二叉树的路径和II
    https://www.lintcode.com/problem/binary-tree-path-sum-ii/description
    描述
    给一棵二叉树和一个目标值,设计一个算法找到二叉树上的和为该目标值的所有路径。路径可以从任何节点出发和结束,但是需要是一条一直往下走的路线。也就是说,路径上的节点的层级是逐个递增的。
    样例
    输入:
    {1,2,3,4,#,2}
    6
    输出:
    [
    [2, 4],
    [1, 3, 2]
    ]
    解释:
    这棵二叉树如图所示:
    1
    /
    2 3
    / /
    4 2
    对于给定目标值6, 很显然有 2 + 4 = 6 和 1 + 3 + 2 = 6 两条路径。
    解题思路:
    从根结点开始往下遍历二叉树,每遍历一个结点,就把当前结点当作终点,然后回头看当前路径是否有满足条件的子路径

    class Solution {
    public:
        /*
         * @param root: the root of binary tree
         * @param target: An integer
         * @return: all valid paths
         */
        vector<vector<int>> binaryTreePathSum2(TreeNode * root, int target) {
            // write your code here
            vector<vector<int>> vecRes;
            vector<int> vec;
            pathSum(vecRes, vec, root, target);
            return vecRes;
        }
        
        void pathSum(vector<vector<int>> &vecRes, vector<int> &vec, TreeNode * node, int target) {
            if (NULL == node) {
                return;
            }
            vec.push_back(node->val);
            int sum = 0;
            for (int i = vec.size() - 1; i >= 0; i--) {
                sum += vec[i];
                if (sum == target) {
                    vector<int> newVec(vec.begin() + i, vec.end());
                    vecRes.push_back(newVec);
                }
            }
            
            
            if (NULL != node->left) {
                pathSum(vecRes, vec, node->left, target);
                vec.pop_back();
            }
            
            if (NULL != node->right) {
                pathSum(vecRes, vec, node->right, target);
                vec.pop_back();
            }
        }
    };
    

    相关文章

      网友评论

          本文标题:二叉树的路径和

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