您的位置 首页 java

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

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

给你 二叉树 的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例1

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

  • 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
  • 输出:[[5,4,11,2],[5,8,4,5]]

提示

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

方法:深度优先搜索

从根开始计算,到找到某个节点的解,深度优先搜索( 回溯 )采用“ 一直向下走,走不通就掉头 ”的思想,相当于采用了“ 先跟遍历 ”的方法来构造搜索树。

算法如下:

  • 递归当前节点,如果当前节点为空,直接返回;
  • 否则目标和递减,用于判断是否满足目标和;
  • 把当前节点的值加入到每一个路径集合中;
  • 当目标和递减到0并且当前节点没有子节点,说明满足条件,直接把当前路径集合“复制”( 因为路径集合是动态的 )到结果集合中;
  • 递归遍历左/右子节点;
  • 向上回溯,需要将当前节点从路径集合中移除;
  • 递归遍历整个树节点完成后,返回结果集合;

代码如下:

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

复杂度分析

  • 时间复杂度:O(n),因为要先序遍历所有的节点。
  • 空间复杂度:O(n),最差的情况下,所有节点的都满足,即整个二叉树都存到结果集合中。

END

绳锯木断,水滴石穿,赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。

文章来源:智云一二三科技

文章标题:算法:二叉树中和为某一值的路径

文章地址:https://www.zhihuclub.com/197813.shtml

关于作者: 智云科技

热门文章

网站地图