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

2017年12月12日11:38:42 发表评论 721 °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: