二叉树中和为某一值的路径

二叉树中和为某一值的路径

http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca

题目的主要信息:
  • 题目给出我们一棵树的树根结点指针,和一个期待值
  • 我们要找出这棵树中,从根节点到叶子节点的路径上的节点值之和等于该期待值的路径,找出所有这样的路径并返回。
举一反三:

学习完本题的思路你可以解决如下题目:

JZ82. 二叉树中和为某一值的路径(一)

JZ84. 二叉树中和为某一值的路径(三)

JZ86. 二叉搜索树的最近公共祖先

方法一:深度优先搜索(推荐使用)

知识点:深度优先搜索(dfs)

深度优先搜索一般用于树或者图的遍历,其他有分支的(如二维矩阵)也适用。它的原理是从初始点开始,一直沿着同一个分支遍历,直到该分支结束,然后回溯到上一级继续沿着一个分支走到底,如此往复,直到所有的节点都有被访问到。

思路:

我们从根节点开始向左右子树进行递归,递归函数中需要处理的是:

  1. 当前的路径path要更新
  2. 当前的目标值expectNumber要迭代,减去当前节点的值
  3. 若当前节点是叶子节点,考虑是否满足路径的期待值,并考虑是否将路径添加到返回列表中

具体做法:

  • step 1:维护两个向量retpath
  • step 2:编写递归函数dfs
  • step 3:递归函数内部要处理更新path,更新expectNumber,判断是否为叶子节点和判断是否要将path追加到ret末尾

图示: alt

Java实现代码:

import java.util.*;
public class Solution {
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    
    void dfs(TreeNode root, int number) {
        // 处理树为空
        if (root == null) return;
        // 路径更新
        path.add(root.val);
        // number更新
        number -= root.val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber,则更新ret
        if(root.left == null && root.right == null && number == 0) {
            ret.add(new ArrayList<>(path));
        }
        // 左右子树递归
        dfs(root.left, number);
        dfs(root.right, number);
        path.removeLast();
    }
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }
}

C++实现代码:

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(TreeNode* root, int number) {
        // 处理树为空
        if (root == NULL) return;
        // 路径更新
        path.emplace_back(root->val);
        // number更新
        number -= root->val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber,则更新ret
        if(root->left == NULL && root->right == NULL && number == 0) {
            ret.emplace_back(path);
        }
        // 左右子树递归
        dfs(root->left, number);
        dfs(root->right, number);
        path.pop_back();
    }
    
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }
};

Python实现代码:

class Solution:
    def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
        ret, path = [], []
        def dfs(root: TreeNode, target: int):
            # 处理树为空
            if not root: return
            # 路径更新
            path.append(root.val)
            # 更新
            target -= root.val
            # 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber,则更新ret
            if not root.left and not root.right and target == 0:
                ret.append(path[:])
            # 左右子树递归
            dfs(root.left, target)
            dfs(root.right, target)
            path.pop()
        dfs(root, target)
        return ret

复杂度分析:

  • 时间复杂度:O(n2)O(n^2),其中nn是树的节点数。最差情况下树的一半为链,一半为完全二叉树,并且所有的路径上的节点值之和都是expectedNumber,这样路径数量为O(n)O(n),且每条路径的节点数也为O(n)O(n),添加到ret的时间代价就是O(n2)O(n^2)
  • 空间复杂度:O(n)O(n),递归栈的深度不会超过节点数量,但最大可能就是节点数量。
方法二:广度优先遍历(扩展思路)

知识点:队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表,插入端称为队尾,删除端称为队首,因整体类似排队的队伍而得名。它满足先进先出的性质,元素入队即将新元素加在队列的尾,元素出队即将队首元素取出,它后一个作为新的队首。

思路:

深度优先搜索是优先一条路径寻到底,而广度优先搜索是按照二叉树的层进行搜索,因此路径需要逐层进行记录,我们引入队列来维护这个逐层路径的信息。

具体做法:

  • step 1:通过维护队列来进行广度优先搜索
  • step 2:当我们遍历到叶子节点的层时,就进行与目标值的匹配
  • step 3:最终返回目标结果

Java实现代码:

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(root == null) return ret;
        Queue<ArrayList<Integer>> pathQ = new LinkedList<ArrayList<Integer>>();
        Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
        pathQ.offer(new ArrayList<Integer>(Arrays.asList(root.val)));
        nodeQ.offer(root);
        
        while(!nodeQ.isEmpty()) {
            ArrayList<Integer> curpath = pathQ.poll();
            TreeNode curnode = nodeQ.poll();
            if(curnode.left != null) {
                ArrayList<Integer> left = new ArrayList<Integer>(curpath);
                left.add(curnode.left.val);
                pathQ.offer(left);
                nodeQ.offer(curnode.left);
            }
            // 右子节点path
            if(curnode.right != null) {
                ArrayList<Integer> right = new ArrayList<Integer>(curpath);
                right.add(curnode.right.val);
                pathQ.offer(right);
                nodeQ.offer(curnode.right);
            }
            // 叶子节点统计
            if(curnode.left == null && curnode.right == null) {
                ArrayList<Integer> l = curpath;
                int sum = 0;
                for(int i = 0; i < l.size(); i++) {
                    sum = sum + l.get(i);
                }
                if(sum == expectNumber) ret.add(l);
            } 
        }
        return ret;
    }
}

C++实现代码:

#include<numeric>
class Solution {
public:
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ret;
        if(root == NULL) return ret;
        pair<vector<int>, TreeNode*> p({root->val}, root);
        // 维护一个path,node的队列
        queue< pair<vector<int>, TreeNode*> > q;
        q.push(p);
        // 如果队列非空
        while(!q.empty()) {
            pair<vector<int>, TreeNode*> cur = q.front();
            q.pop();
            TreeNode* node = cur.second;
            // 左子节点path
            if(node->left) {
                vector<int> left = cur.first;
                left.push_back(node->left->val);
                q.push(make_pair(left, node->left));
            }
            // 右子节点path
            if(node->right) {
                vector<int> right = cur.first;
                right.push_back(node->right->val);
                q.push(make_pair(right, node->right));
            }
            // 叶子节点统计
            if(node->left == NULL && node->right == NULL) {
                vector<int> l = cur.first;
                int sum = accumulate(l.begin(), l.end(), 0);
                if(sum == expectNumber) ret.push_back(l);
            } 
        }
        return ret;
    }
};

Python实现代码:

class Solution:
    def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
        if not root: return []
        # 直接将所需要的节点,路径,节点值组成一个列表
        s = [(root, [root.val], root.val)]
        ret = []
        while s:
            node, val, sum = s.pop()
            # 如果是到了叶子节点的情况下,并且路径总和与target一致
            if node and not node.left and not node.right and sum == target:
                ret.append(val)
            # 处理左子树路径
            if node.left:
                s.append((node.left, val + [node.left.val], sum + node.left.val))
            # 处理右子树路径
            if node.right:
                s.append((node.right, val + [node.right.val], sum + node.right.val))
        return ret

复杂度分析:

  • 时间复杂度:最差为O(n2)O(n^2),分析方法与方法一相同
  • 空间复杂度:O(n)O(n),n是树的节点数量,因为一次遍历下来访问了所有节点,列表s的空间代价
全部评论
最后的ans要改成path吧
4 回复 分享
发布于 2020-09-19 14:26
这答案每次都不是一个人写的吧,水平参差不齐
3 回复 分享
发布于 2020-10-31 16:54
需要java代码,请求官方出多语言
2 回复 分享
发布于 2020-06-22 10:32
最后一句path.pop_back()不懂
1 回复 分享
发布于 2020-08-30 11:59
字典序怎么没考虑?
1 回复 分享
发布于 2020-08-07 11:46
思路清晰>_<
1 回复 分享
发布于 2020-06-02 11:47
这边是否需要考虑一下字典序?
9 回复 分享
发布于 2020-07-21 05:07
已经是全局变量了为什么还要进行参数传递呢?
2 回复 分享
发布于 2021-02-10 21:21
你好,因为path为全局变量,所以path的修改,不会导致已经push进ret的path被修改了吗,谢谢~
1 回复 分享
发布于 2022-03-09 16:16
这题BFS的代码确实很厉害。属实是没有想到。
点赞 回复 分享
发布于 2023-03-17 02:04 江苏
请问方法一的 Python 代码第13行为什么要 append path的切片(path[:])而不能append(path)呢?
点赞 回复 分享
发布于 2022-09-07 12:04 北京
这时间复杂度为O(N) 吧,只遍历了一遍树就完了
点赞 回复 分享
发布于 2022-07-15 14:54
全局变量?
点赞 回复 分享
发布于 2021-08-23 11:07
没考虑字典序是因为题目默认给的是搜索二叉树,如果先搜左边结点再搜右边结点结果天然是字典序;反之则不是。全变变量不用再传参了。
点赞 回复 分享
发布于 2021-07-19 17:36
提示错误In file included from a.cc:2: ./solution.h:27:33: error: use of undeclared identifier 'ans' dfs(root, expectNumber, ans, ret);
点赞 回复 分享
发布于 2020-09-09 16:32
作者确实没有考虑字典序,其实也很简单:在return ret;这一行前面增加一行sort(ret.begin(), ret.end());即可。
点赞 回复 分享
发布于 2020-08-31 07:03

相关推荐

兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
57
17
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务