Lexi's Leetcode solutions

Posts Tagged ‘后序

算法:

  • arch代表穿过当前节点的路径(左边一支儿+自己节点+右边一支儿)。
  • 注意树的节点可以是负数,所以arch不一定是最长的。
  • 每次return以root(当前节点)开头最大的单只path sum。
  • res[]就是一个存result的reference object,java不支持c++那种直接&传reference,
    所以要么用个长度为一的数组,要么写个wrapper。还是用数组简单。
  • update res[0],用arch和以自己开头一支儿的比,谁大就把res[0] update成谁。
public int maxPathSum(TreeNode root) {
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    maxPath(root, res);
    return res[0];
}
private int maxPath(TreeNode root, int[] res) {
    if (root == null)
        return 0;
    int left = maxPath(root.left, res);//左边一支儿(不算自己)
    int right = maxPath(root.right, res);
    int arch = left + right + root.val; //穿过自己
    int single = Math.max(root.val, Math.max(left, right) + root.val);
    //(算上自己)
    res[0] = Math.max(res[0], Math.max(arch, single));//update结果
    return single;
}
Advertisements
Tags: ,

经典题,注意balanced的定义:左右子树都balance,且高度差<=1。所以下面这个也是balanced的,即使a的做右子树都不是完全树。

    a
   / \ 
  b   d
 /     \
c       e

唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”,直接用height = -1表示不平衡就行。

public boolean isBalanced(TreeNode root) {
  return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
  if (root == null)
    return 0;
  int leftHeight = getHeight(root.left);
  if (leftHeight < 0)
    return -1;
  int rightHeight = getHeight(root.right);
  if (rightHeight < 0)
    return -1;
  if (Math.abs(leftHeight - rightHeight) > 1)
    return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}
Tags: , ,

这题看似很难,因为树的rotation完全不会;但是咬牙想了五分钟就bug free的写出来了,一遍过,看来树的recursive理解已经挺到位了。

算法:1~n中每个数字都可以是root,定了谁是root之后(比如k),他的左子树只能是1~k-1组成的,右子树只能是k+1~n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意:终止条件有两种:

  1. p == q,说明就一个节点了,没啥可转的,就一种return 1
  2. p > q,说明这一段已经不存在了,这时不应该return 0,因为这正是子树是null的情况!所以还应该return 1
public int numTrees(int n) {
  return getWays(1, n);
}
int getWays(int p, int q) {
  if (p >= q)
    return 1;
  int ways = 0;
  for (int i = p; i <= q; i++) {
    int leftWays = getWays(p, i - 1);
    int rightWays = getWays(i + 1, q);
    ways += leftWays * rightWays;
  }
  return ways;
}
Tags: , ,