剑指Offer(二十四):二叉树中和为某一值的路径

2017年12月12日11:38:42 14 3,192 °C
摘要

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

剑指Offer(二十四):二叉树中和为某一值的路径

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

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

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

2、代码

C++:

Python:

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

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

目前评论:14   其中:访客  9   博主  5

    • avatar Zac 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 移动 0

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

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

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

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

          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

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

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 北京市丰台区 联通

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

              • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 3

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

                  • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 3

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

                    • avatar 小白菜 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 3

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

                    • avatar 哎呦喂 来自天朝的朋友 谷歌浏览器 Windows 7 黑龙江省哈尔滨市 联通 0

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

                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

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

                        • avatar 小占同学 来自天朝的朋友 谷歌浏览器 Windows 10 安徽省合肥市 中国科学技术大学 1

                          那我来一个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

                            wow sorry,没看清题目。感谢大佬分享!