一、题目
Given a binary tree and a sum, determine(查明) if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Result: return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
二、分析
【1】常用的递归
设计一个 currSum 记录当前路径的总和。
【1】 判断当前结点是否为叶子结点
- 如果是叶子结点,那么下一步就返回 currSum 是否等于 sum .
- 如果非叶子结点,那么将 sum 的值减去 currSum ,然后递归搜索左子树、右子树。
public class PathSum {
public static boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
int curr = root.val;
if (root.right == null && root.left == null)
return curr == sum;
return hasPathSum(root.left, sum-curr) || hasPathSum(root.right, sum-curr);
}
}
复杂度分析:
时间复杂度: O(N)
- 每个结点只访问一次,因此时间复杂度为 O(N),其中 N 是结点的数量。
空间复杂度:O(N) / O(log(N)
- 最坏情况下,整棵树是非平衡的,例如每个节点都只有一个孩子,递归会调用 N 次(树的高度),因此栈的空间开销是 O(N) 。
- 最好情况下,树是完全平衡的,高度只有 log(N),因此在这种情况下空间复杂度只有 O(log(N)) 。
【2】迭代代替递归
【1】定义两个栈 (nodeStack、integerStack) 和一个 curr 计数器,用来记录 sum 减去当前遍历结点的值后的结果。
【2】当正在遍历的结点的左右子结点为空且 curr == 0,证明路径上有组成总和为 sum 的各个结点。
【3】如果上述条件不成立,那么,将其右节点 push 入栈,相当于先遍历右子树。重复上述过程!
public static boolean hasPathSum2(TreeNode root, int sum) {
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> integerStack = new Stack<>();
nodeStack.push(root);
integerStack.push(sum - root.val);
TreeNode node;
int curr;
while (!nodeStack.isEmpty()) {
node = nodeStack.pop();
curr = integerStack.pop();
if (node.left == null && node.right == null && curr == 0)
return true;
if (node.right != null) {
nodeStack.push(node.right);
integerStack.push(curr-(node.right.val));
}
if (node.left != null) {
nodeStack.push(node.left);
integerStack.push(curr-(node.left.val));
}
}
return false;
}
复杂度分析:
时间复杂度: O(N)
- 每个结点只访问一次,因此时间复杂度为 O(N),其中 N 是结点的数量。
空间复杂度:O(N) / O(log(N)
使用了两个栈,一个用于存储树的结点
- 最坏情况 —> O(N)
- 最好情况 —> O(log(N)),树是平衡的!
三、树题总结
这是统一的 main 函数
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(hasPathSum(root, 29)); //false
}
其实,做为树的递归题目是非常有套路可循的,因为树有两个分支,所以在递归里也有两个分支,一般是通过 递归 A (|| &&) 递归 B 来实现分支。只要明白了这一点,递归函数就不会很难设计。