【练习】003 路径总和【Depth-First-Search】

一、题目

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 来实现分支。只要明白了这一点,递归函数就不会很难设计。

上一篇:AtCoder Grand Contest 003题解


下一篇:day 003 作业