二叉树的遍历（篇4）判断从根到叶节点的和是否等于某个给定的值

本文主要是介绍二叉树的遍历（篇4）判断从根到叶节点的和是否等于某个给定的值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定二叉树和一个数sum，如果从树的根开始到叶节点的值等于sum，则返回true。如果没有找到这样的路径，则返回false。

这里写图片描述

例如，
在上述树根到叶节点存在具有以下和。

21 - > 10 - 8 - 3
23 - > 10 - 8 - 5
14 - > 10 - 2 - 2

因此，返回的值应该只对数字21，23和14. true。对于任何其他数字，返回值应该为false。

算法：
递归检查左孩子或右孩子的路径总和是否等于（当前节点的数值）

代码

// Java program to print to print root to leaf path sum equal to
// a given number/* A binary tree node has data, pointer to left childand a pointer to right child */
class Node 
{int data;Node left, right;Node(int item) {data = item;left = right = null;}
}class BinaryTree {Node root;/*Given a tree and a sum, return true if there is a path from the rootdown to a leaf, such that adding up all the values along the pathequals the given sum.Strategy: subtract the node value from the sum when recurring down,and check to see if the sum is 0 when you run out of tree.*/boolean haspathSum(Node node, int sum) {if (node == null)return (sum == 0);else{boolean ans = false;/* otherwise check both subtrees */int subsum = sum - node.data;if (subsum == 0 && node.left == null && node.right == null)return true;if (node.left != null)ans = ans || haspathSum(node.left, subsum);if (node.right != null)ans = ans || haspathSum(node.right, subsum);return ans;}}/* Driver program to test the above functions */public static void main(String args[]) {int sum = 21;/* Constructed binary tree is10/  \8     2/ \   /3   5 2*/BinaryTree tree = new BinaryTree();tree.root = new Node(10);tree.root.left = new Node(8);tree.root.right = new Node(2);tree.root.left.left = new Node(3);tree.root.left.right = new Node(5);tree.root.right.left = new Node(2);if (tree.haspathSum(tree.root, sum))System.out.println("There is a root to leaf path with sum " + sum);elseSystem.out.println("There is no root to leaf path with sum " + sum);}
}