每日算法之二叉树中和为某一值的路径(二)(二叉树求和路径)

  本篇文章为你整理了每日算法之二叉树中和为某一值的路径(二)(二叉树求和路径)的详细内容,包含有二叉树和为某一个值的路径 二叉树求和路径 二叉树路径总和 求二叉树结点值之和 每日算法之二叉树中和为某一值的路径(二),希望能帮助你了解 每日算法之二叉树中和为某一值的路径(二)。

  

输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。

 

  1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

  2.叶子节点是指没有子节点的节点

  3.路径只能从父节点到子节点,不能从子节点到父节点

  4.总节点数目为n

  

 

  

当前的路径path要更新

 

  当前的目标值expectNumber要迭代,减去当前节点的值

  若当前节点是叶子节点,考虑是否满足路径的期待值,并考虑是否将路径添加到返回列表中

  具体做法:

  step 1:维护两个向量ret和path

  step 2:编写递归函数dfs

  step 3:递归函数内部要处理更新path,更新expectNumber,判断是否为叶子节点和判断是否要将path追加到ret末尾

  

 

  

package mid.JZ34二叉树中和为某一值的路径2;

 

  import java.util.ArrayList;

  import java.util.LinkedList;

  class TreeNode {

   int val = 0;

   TreeNode left = null;

   TreeNode right = null;

   public TreeNode(int val) {

   this.val = val;

  public class Solution {

   ArrayList ArrayList Integer ret = new ArrayList ();

   LinkedList Integer path = new LinkedList ();

   public ArrayList ArrayList Integer FindPath(TreeNode root, int expectNumber) {

   dfs(root,expectNumber);

   return ret;

   public void dfs(TreeNode root, int expectNumber) {

   if (root == null) {

   return;

   path.add(root.val);

   expectNumber -= root.val;

   if (root.left == null root.right == null expectNumber == 0) {

   ret.add(new ArrayList (path));

   dfs(root.left, expectNumber);

   dfs(root.right, expectNumber);

   path.removeLast();

  

 

  以上就是每日算法之二叉树中和为某一值的路径(二)(二叉树求和路径)的详细内容,想要了解更多 每日算法之二叉树中和为某一值的路径(二)的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: