中山市建设安全监督站网站,wordpress删除自豪的,网站建设滕州信息港,中国专门做统计网站二叉树中和为某一值的路径
题目#xff1a;输入一颗二叉树和一个整数#xff0c;打印出二叉树中节点值的和为给定值的所有路径。从树的根节点开始往下一只到叶子节点所经过的节点形成一条路径。我们用二叉树节点的定义沿用之前文章中 二叉查找树实现原理定义。如下#xff…二叉树中和为某一值的路径
题目输入一颗二叉树和一个整数打印出二叉树中节点值的和为给定值的所有路径。从树的根节点开始往下一只到叶子节点所经过的节点形成一条路径。我们用二叉树节点的定义沿用之前文章中 二叉查找树实现原理定义。如下
public class BinaryNode implements Comparable {private Object element;private BinaryNode left;private BinaryNode right;private int count;案例输入如下图中二叉树和整数22打印出两条路径第一条包含节点10 12第二条包含10,57 二叉树的节点定义中我们是无法得到树的路径这个概念值的应为二叉树中并没有介绍树的路径的数据结构因此对于大多数人而言这个是一个新的理论模型也就很难一下找到思路我们从一个案例入手更加简单还是用上面的案例由于路径就是根节点出发到叶子节点也就是说路径总是以根节点为起点因此是先根遍历也就是我们可以用二叉树的前序遍历根左右的遍历方式在我之前的文章 数据结构与算法–二叉树实现原理 中详细介绍了三种遍历方式并附带源码我们以前序遍历为思路解这个问题。按前序遍历范问上图10,54,712 是前序遍历的顺序我们可以从二叉树结构中看到没有指向父节点的指针因此范问5 的时候并不知道10 节点的路径和值因此我们需要把上一个节点经过的路径保存下来每次范问一个节点都将当前节点的路径添加到下一个节点的路径中因此到达5 时候因存 105接着到大4总和为9 22.因此返回5节点到达7 和为 1057 22 符合提议接着返回10 访问12,1012 22 符合题意因此有两组解按如上分析有如下步骤 安前序遍历递归实现二叉树的遍历范问每个子节点之前将本节点走过的路径path和 路径和count传递给需要范问的子节点字节点范问之前将父节点路径path添加上自己的路径 pathelement路径和添加自己的节点权重 pathweight如果范问节点没有子节点则比较路径和count 是否和目标 值一致一致则正解。如下实现此处构造二叉树的方法沿用之前文章数据结构与算法–二叉查找树实现原理中方法
/*** 二叉树中查找和为n 的路径** author liaojiamin* Date:Created in 10:51 2021/5/17*/
public class FindPathInBinary {public static boolean findPath(BinaryNode binaryNode, Integer target) {ListInteger list new ArrayList();list.add(Integer.valueOf(binaryNode.getElement().toString()));Integer count Integer.valueOf(binaryNode.getElement().toString());return findPath(binaryNode, list, count, target);}public static boolean findPath(BinaryNode binaryNode, ListInteger beforePath, Integer beforeCount, Integer target) {if (binaryNode.getLeft() null binaryNode.getRight() null) {printPath(beforePath);System.out.println(beforeCount beforeCount);if(beforeCount target){System.out.print(存在路径);printPath(beforePath);System.out.println();}return false;}if (binaryNode.getLeft() ! null) {BinaryNode left binaryNode.getLeft();Integer count beforeCount Integer.valueOf(left.getElement().toString());ListInteger list new ArrayList();list.addAll(beforePath);list.add(Integer.valueOf(left.getElement().toString()));findPath(binaryNode.getLeft(), list, count, target);}if(binaryNode.getRight() ! null){BinaryNode right binaryNode.getRight();Integer count beforeCount Integer.valueOf(right.getElement().toString());ListInteger list new ArrayList();list.addAll(beforePath);list.add(Integer.valueOf(right.getElement().toString()));findPath(binaryNode.getRight(), list, count, target);}return false;}public static void printPath(ListInteger objectList) {for (Object o : objectList) {System.out.print(o);System.out.print(,);}}public static void main(String[] args) {
// Integer arr[] new Integer[]{44,94,92,23,42,13,7,76,70,40,78,28,78,36,14,53,10,91,36,15};Integer arr[] new Integer[]{10,5,4,7,12};BinaryNode node new BinaryNode(null, null, null);BinarySearchTree searchTree new BinarySearchTree();for (int i 0; i arr.length; i) {int num arr[i];node searchTree.insert(num, node);System.out.print(num,);}System.out.println();System.out.println();findPath(node, 22);}}
该问题考察的是二叉树遍历的变种考察复杂问题的思维能力当一下没有思路我们可以从具体案例开始分析这样就能找出其中规律
上一篇数据结构与算法-- 二叉树后续遍历序列校验 下一篇数据结构与算法–复杂链表的复制
