当前位置: 代码迷 >> 综合 >> 打印出二叉树中结点值的和为输入整数的所有路径
  详细解决方案

打印出二叉树中结点值的和为输入整数的所有路径

热度:59   发布时间:2023-10-29 02:30:36.0

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

思路:这道题的思路采用递归算法来解答,就是采用对树的先序遍历,遍历整个树,每遍历一个节点,将当前节点值加入临时存储节点的list中,更新sum,检查目标值并判断是否为叶子节点,如果条件判断正确,则将当前序列加入到结果集中。然后遍历左子树和右子树,如果遍历到叶子节点不等于相应的整数,则将操作数移除list,并更新sum值。

ArrayList<ArrayList<Integer>> pathNode=new ArrayList<ArrayList<Integer>>();//存储节点结果ArrayList<Integer> list=new ArrayList<Integer>();//相当于一个临时操作栈int sum=0;public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {if(root==null) return pathNode;//如果树为空,返回空路径boolean leaf=(root.left==null&&root.right==null);//用来存储节点是否为叶子节点sum+=root.val;list.add(root.val);if(sum==target&&leaf){pathNode.add(new ArrayList(list));}FindPath(root.left,target);//从左子树中继续查找FindPath(root.right,target);//从右子树中继续查找sum-=root.val;list.remove(list.size()-1);//将当前操作数出序列return pathNode;}

 

  相关解决方案