1/18，Max/Min Depth

  • 树的Depth和Height概念的区别，一个自底向上看，一个自顶向下看。
  • 树的深度等于root到最底部节点的高度。
  • 如果一棵树只有一个节点，深度为1。（不一定，也可能是0，和面试官make sure）
  • 叶节点的高度为1。

Maximum Depth of Binary Tree

  • 迭代 ✔️
  • 递归 ✔️

用一个stack记录当前的节点和depth，每次go deeper就depth+1。用一个variable来update当前的max depth，当pop出的cur是叶节点的时候才比较深度。或者我们可以用level order traversal 来做

class Solution {
    class Tuple {
        TreeNode node;
        int depth;
        public Tuple(TreeNode node, int d) {
            this.node = node;
            this.depth = d;
        }
    }
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int max = 0;
        Deque<Tuple> stack = new LinkedList<>();
        stack.push(new Tuple(root, 1));

        while (!stack.isEmpty()) {
            Tuple t = stack.pop();
            if (t.node.left == null && t.node.right == null) {
                max = Math.max(max, t.depth);
            }

            if (t.node.left != null) {
                stack.push(new Tuple(t.node.left, t.depth + 1));
            }
            if (t.node.right != null) {
                stack.push(new Tuple(t.node.right, t.depth + 1));
            }
        }
        return max;
    }
}

递归分治和迭代相反，是自底向上计算深度，root node的深度等于它左右子树中最大的深度加1。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Minimum Depth of Binary Tree

  • 迭代 ✔️
  • 递归 ✔️

迭代解法和求max depth没啥区别，就是把初始的min depth定义为无穷大，把pop出的叶节点的depth和min depth比较。(略)

递归要考虑到一个edge case，可能root只在一边有子树，类似一个链表结构时，mindepth应该等于list长度，不是1。

所以在root为空时，需要有两种返回结果。其一是初始的root就为空，返回0。其二，dfs访问某个节点后，该节点的left或right为空，此时不能返回0，而要返回无穷大，这样的话最小才能取到节点非空的那边。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        // we need to consider the 0 cases separately.
        if (left == 0) return right + 1;
        if (right == 0) return left + 1;

        return Math.min(left, right) + 1;
    }
}

helper函数有两个出口，第一个是在节点为空时，返回无穷大。第二个是如果当前节点非空，判断它是否为叶节点，如果是就返回1作为深度，结束dfs。注意两出口的先后顺序。

1/1补充，还是要特别注意出口顺序，如果调换的话，因为每次都要走左右两边，如果调用dfs中的参数node已经是None，None.left/None.right会造成NoneType Error，所以要先检查节点本身。

2/17 秒掉。

1/18，Path & Path Sum

路径可以是root to leaf, root to any, any to any，也是个要make sure的地方。

  • all possible paths
  • one/all possible required paths
  • max path sum

Binary Tree Paths

  • 迭代 ✔️
  • 递归 ✔️

因为是root to leaf，想法是用list去保存遍历过的节点，并传入dfs，当遍历到叶节点时，把list转为要求的string，再加到res里面。

to do

要注意的细节是，对于path的更新是用path+[cur.val]，而不是path.append()，因为path是mutable object的引用，append操作会修改path，影响另一子树的path参数。如果用path.append()，就需要每次都pop()掉多余的节点，消除影响。

递归的Traverse解法，套路。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;

        dfs(res, root, new StringBuilder());
        return res;
    }
    private void dfs(List<String> res, TreeNode root, StringBuilder sb) {
        if (node.left == null && node.right == null) {
            sb.append(node.val);
            list.add(sb.toString());
            return;
        }

        sb.append(node.val);

        if (node.left != null) {
            int len = sb.length();
            sb.append("->");
            dfs(node.left, list, sb);  //1->4
            sb.setLength(len);
        }
        if (node.right != null) {
            int len = sb.length();
            sb.append("->");
            dfs(node.right, list, sb);
            sb.setLength(len);
        }
    }
}

what is root to specific node?

class Solution {

    public List<Integer> getPath(TreeNode root, TreeNode p) {

        List<Integer> list = new ArrayList<>();
        if(hasPath(root, list, p.val)) {
            return list;
        }
        return null;
    }

    private boolean hasPath(TreeNode root, List<Integer> list, int x) {

        if (root == null) return false;
        list.add(root.val);
        if (root.val == x) return true;

        if (hasPath(root.left, list, x) || hasPath(root.right, list, x) {
            return true;
        }
        return false;
    }
}

Binary Tree Path Sum

  • 迭代 ✔️
  • 递归 ✔️

除了需要判定是否是正确路径，跟上一题几乎一样。递归解法改动下出口就可以了。

class Solution {
    class Tuple{
        TreeNode node;
        int sum;

        public Tuple(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        Deque<Tuple> stack = new LinkedList<>();
        stack.push(new Tuple(root, root.val));

        while (!stack.isEmpty()) {
            Tuple t = stack.pop();
            if (t.node.left == null && t.node.right == null) {
                if (t.sum == sum) {
                    return true;
                }
            }
            if (t.node.left != null) stack.push(new Tuple(t.node.left, t.sum + t.node.left.val));
            if (t.node.right != null) stack.push(new Tuple(t.node.right, t.sum + t.node.right.val));
        }
        return false;
    }
}

recursive:

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        if (root.left == null && root.right == null) {
            if (root.val == sum) 
                return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

12/15复习注，有效的path要满足两个条件才能被加进res。1.当前为叶节点，2.target减去当前val等于0。

2/18 复习，改成递归来做，还有其他出口设置，解题时还是要仔细，一定要提前判断node是否为空。

Binary Tree Path Sum II

note: num 是辅助 list的，可以减少时间复杂度，也可以不用num

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        List<Integer> list = new ArrayList<>();
        dfs(root, res, list, sum);
        return res;
    }

    private void dfs(TreeNode root, List<List<Integer>> res, List<Integer> list, int sum) {
        if (root == null) return;

        list.add(root.val);

        if (root.left == null && root.right == null) {
            if (root.val == sum) {
                res.add(new ArrayList<>(list));
                list.remove(list.size() - 1);
                return;
            }            
        }

        if (root.left != null) dfs(root.left, res, list, sum - root.val);
        if (root.right != null) dfs(root.right, res, list, sum - root.val);

        list.remove(list.size() - 1);
    }
}

Binary Tree Path Sum III

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;

        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int findPath(TreeNode root, int sum) {
        int res = 0;
        // base case
        if (root == null) {
            return res;
        }

        if (sum == root.val) {
            res++;
        }
        res += findPath(root.left, sum - root.val);
        res += findPath(root.right, sum - root.val);

        return res;
    }
}

note: 函数findPath() 返回的是solution个数，

Binary Tree Maximum Path Sum

跟上一题不同的是path的定义，这题的path可以是any to any，树上任意两点的路径和。

结合分治法的思路，最大路径和有几种可能：

  1. 不经过root的左路中的最大的any to any 路径/单独节点
  2. 不经过root的右路中的最大的any to any 路径/单独节点
  3. 经过root，root + 左路中最大的root to any path(单路) + 右路中最大的root to any path(单路)
  4. 经过root，root + 左路/右路中较大的root to any path
  5. 经过root，单独的root最大

4，5其实就是root to any的情况，具象化看起来是一条单路。这样的话，4和5可以看成是构成3中的一条单路的方式。因此，能把最大路径和简化为求1/2/3其中之一，maxPath = max(case1, case2, case3)。

  • 递归 ✔️
class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;

        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        int left = Math.max(0, dfs(root.left));    // case345
        int right = Math.max(0, dfs(root.right));  // case345

        max = Math.max(max, root.val + left + right);  // from the perspective of the parent view. case 1 and 2

        return root.val + Math.max(left, right);  //  from the perspective of the current node view. case 345
    }
}

关键是需要考虑到节点val为负的情况。比如，一棵树只有一个根节点val=-1，假如把出口的返回值设为(0，0)，那么得到的maxPath=0，而实际应该是-1。因此递归的出口需要改动一下，返回 (-∞, 0) 的话才行。

同样考虑节点值为负的情况，最大单路径single就不应该再考虑当前节点了，而是忽略这个点，做法是让root.val=0。举个反例，根-左-右分别是-1，-2，-3的树，maxPath应该是-1，但如果是root.val，maxPath=-2。

递归拆解还是分为left和right，不同的是它们都是以tuple的形式返回得到的，下一级给上一级传递信息的方式，这个想法非常重要。

Binary Tree Maximum Path Sum II

这题是求from root to any node的最大路径值，返回的path至少要有root.val。还要考虑到节点值为负的情况，如果所有节点的val都为负的话，那max path sum就是root.val。

  • 迭代 ✔️
  • 递归 ✔️
public class Solution {
    class Tuple{
        TreeNode node;
        int sum;

        public Tuple(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }
    public int maxPathSum2(TreeNode root) {
        // write your code here
        if (root == null) return -1;

        // 
        Deque<Tuple> stack = new LinkedList<>();
        stack.push(new Tuple(root, root.val));

        int max = root.val;
        while (!stack.isEmpty()) {
            Tuple t = stack.pop();
            max = Math.max(max, t.sum);

            if (t.node.left != null) stack.push(new Tuple(t.node.left, t.sum + t.node.left.val));
            if (t.node.right != null) stack.push(new Tuple(t.node.right, t.sum + t.node.right.val));
        }

        return max;
    }
}

如果root不是空节点，就可以初始化max_path为root.val，再在while循环中update。参数sum是整数immutable object。这里，对于每个返回的TreeNode, 我们不仅需要这个node，还需要cumulative sum from root, 所以我们可以定义一个class called Tuple.

转为递归Traverse的解法，还是套路。可以用一个list来记录all possible path sum，再求max。但是这道题特点是只要求path sum，是一个integer，所以可以利用整数immutable object，占用O(n)存储空间。

public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum2(TreeNode root) {
        // write your code here
        if (root == null) return -1;

        dfs(root, 0);
        return max;    // what if the root is negative?
    }

    private void dfs(TreeNode root, int sum) {
        // base case
        if (root == null) return;

        max = Math.max(max, sum + root.val);

        // recursive case
        if (root.left != null) dfs(root.left, sum + root.val);
        if (root.right != null) dfs(root.right, sum + root.val);
    }
}

递归之分治法。自底向上，最大路径可以是左右路径和中较大的那个加上root，也可以是单独的root。

12/16复习注，求的是最大路径值，所以用一个变量保存路径值就够了。如果还要返回这条最大路径，就需要一个array，结合tree paths。迭代的思路是以root为起点，自顶向下计算所有路径的长度，不断update max path。Traverse是自顶向下遍历树，并通过保存一个array of all paths，最后求最大值得到maxpath。DC是自底向上得到一条最大路径。

12/16复习时发现，上面写了一堆废话，都忘了。重新整理下。

第一步，知道最大路径由哪些支路构成，就能很容易写出框架。

第二步，要处理两个难点。一是递归出口的返回值不能简单为0。二是single = max(root+left, root+right, 0)中的0，不用root，why。

首先，对比上面那道root to any，用root可以，因为路径一定要包括root。而对于这题，返回的path可以不含有root，因为求的single只是手段，而非结果。而且在求single时，如果当前root是负值，不要这个负值的root(设为0)才是正确的最大single。当然，如果节点的值不含有负数，就没关系了。

其次，对于递归出口返回值的设定，有几种可能性，可以通过举例来验证。比如tree就只有一个root=-1，所以为了maxpath能返回-1，tuple就要设为(-float('inf'), 0)才行。

1/2已经可以一遍AC了，还是先写好递归拆解，出口的返回值通过test case来确定。

results matching ""

    No results matching ""