剑指Offer（二十四）：二叉树中和为某一值的路径

2017年12月12日11:38:42 15 6,117 °C
摘要

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

剑指Offer（二十四）：二叉树中和为某一值的路径

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

1、思路

深度优先搜索。使用前序遍历，使用两个全局变量result和tmp，result来存放最终结果，tmp用来存放临时结果。

每次遍历，我们先把root的值压入tmp，然后判断当前root是否同时满足：

  • 与给定数值相减为0；
  • 左子树为空；
  • 右子树为空。

如果满足条件，就将tmp压入result中，否则，依次遍历左右子树。需要注意的是，遍历左右子树的时候，全局变量tmp是不清空的，直到到了根结点才请空tmp。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber){
        if(root == NULL){
            return result;
        }
        
        tmp.push_back(root->val);
        if((expectNumber - root->val ) == 0 && root->left == NULL && root->right == NULL){
            result.push_back(tmp);
        }
        
        //遍历左子树
        FindPath(root->left, expectNumber - root->val);
        //遍历右子树
        FindPath(root->right, expectNumber - root->val);
        
        tmp.pop_back();
        return result;
    }
private:
    vector<vector<int> > result;
    vector<int> tmp;
};

Python：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if not root.left and not root.right and expectNumber == root.val:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left, expectNumber-root.val)
        right = self.FindPath(root.right, expectNumber-root.val)
        for i in left+right:
            res.append([root.val]+i)
        return res

感谢@小小毛的本地测试用例：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if not root.left and not root.right and expectNumber == root.val:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left, expectNumber-root.val)
        right = self.FindPath(root.right, expectNumber-root.val)
        for i in left+right:
            res.append([root.val]+i)
        return res
if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
 
    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A4.left=A6
 
    solution=Solution()
    ans=solution.FindPath(A1,8)
    print('ans=',ans)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：15   其中：访客  10   博主  5

    • avatar Zac 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 移动 0
      回复 2019年4月3日 下午3:46  沙发

      你好，这道题Python代码中的第18，19行，我没有明白，请教一下。

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
          回复 2019年4月3日 下午8:30  1层

          @Zac 就是满足的路径结点加起来。

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
          回复 2019年4月9日 下午9:03  板凳

          class TreeNode:
          def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None

          class Solution:
          # 返回二维列表，内部每个列表表示找到的路径
          def FindPath(self, root, expectNumber):
          # write code here
          if not root:
          return []
          if not root.left and not root.right and expectNumber == root.val:
          return [[root.val]]
          res = []
          left = self.FindPath(root.left, expectNumber-root.val)
          right = self.FindPath(root.right, expectNumber-root.val)
          for i in left+right:
          res.append([root.val]+i)
          return res
          if __name__==’__main__’:
          A1 = TreeNode(1)
          A2 = TreeNode(2)
          A3 = TreeNode(3)
          A4 = TreeNode(4)
          A5 = TreeNode(5)
          A6 = TreeNode(6)

          A1.left=A2
          A1.right=A3
          A2.left=A4
          A2.right=A5
          A4.left=A6

          solution=Solution()
          ans=solution.FindPath(A1,8)
          print(‘ans=’,ans)
          这是可以测试的代码，便于理解。谢谢

          • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
            回复 2019年4月9日 下午10:42  地板

            这个代码写得牛啊，我看了一天才懂啊 :arrow: 手动点赞

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Android 8.0.0 MIX 2 Build/OPR1.170623.027 北京市丰台区 联通
                回复 2019年4月10日 上午8:19  1层

                @小小毛 递归可能不太好理解～

              • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 4
                回复 2019年5月27日 上午10:45  4楼

                你好：
                vector<vector > result;
                vector tmp;
                我把这两个定义在public里怎么就不对了；

                  • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 4
                    回复 2019年5月27日 上午10:46  1层

                    @小白菜 vector<vector > result;
                    vector tmp;
                    这样那个显示有误

                    • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 4
                      回复 2019年5月27日 上午10:56  1层

                      @小白菜 懂了那样就成局部变量了；校友啊，你真厉害

                    • avatar 哎呦喂 来自天朝的朋友 谷歌浏览器 Windows 7 黑龙江省哈尔滨市 联通 0
                      回复 2019年6月27日 上午10:00  5楼

                      第18行(expectNumber – root->val ) == 0判断的是输入的整数与根节点的差值是否等于0，不应该判断输入的整数与tmp中和的差值是否等于0么？

                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                          回复 2019年6月27日 下午9:44  1层

                          @哎呦喂 这是递归啊，递归进去了都是减掉根节点的值的。

                        • avatar 小占同学 来自天朝的朋友 谷歌浏览器 Windows 10 安徽省合肥市 中国科学技术大学 1
                          回复 2019年9月2日 上午11:12  6楼

                          那我来一个c++的测试用例，便于理解。
                          int main(){
                          TreeNode BTree[5] = {10, 5, 12, 4, 7};
                          BTree[0].left = &BTree[1];
                          BTree[0].right = &BTree[2];
                          BTree[1].left = &BTree[3];
                          BTree[1].right = &BTree[4];

                          vector<vector > res;
                          Solution solution;
                          res = solution.FindPath(BTree, 22);

                          for (auto it = res.begin(); it != res.end(); ++it){
                          for (int i = 0; i < (*it).size(); ++i)
                          cout << (*it)[i] << " " ;

                          cout << endl;
                          }
                          return 0;
                          }

                          • avatar dymsxg 来自天朝的朋友 火狐浏览器 Windows 10 广东省广州市 联通 0
                            回复 2019年9月18日 下午7:53  7楼

                            wow sorry，没看清题目。感谢大佬分享！

                            • avatar 锟斤拷小锟斤拷 来自天朝的朋友 谷歌浏览器 Windows 10 四川省绵阳市 西南科技大学 1
                              回复 2020年5月25日 下午9:50  8楼

                              为什么递归完树的左分支以后（此时expectNumber=-5），再递归一次就变成了expectNumber=1，我想问怎么就回到上一级的结点了，代码具体怎样操作让它回到上一级结点的，谢谢