Recursive Thinking in Binary Tree

在用递归实现Binary Tree的时候总结下来需要具备宏观思维和微观思维

什么是宏观思维呢？宏观思维就是递归三要素，也就是递归函数的定义（输入是什么，输出是什么，返回值类型是什么，以及最重要的这个函数在做一件什么事情），函数拆解（当前节点的结果是如何通过它的左子树和右子树得来的），以及退出条件（什么情况下可以直接得到结果，或者什么情况下退出递归函数）

什么是微观思维呢？微观思维就是递归过程中如何进栈，如何出栈，是自顶向下还是自下而上，当前节点的函数值如何得到。比如tree的三种traverse，在traverse的过程中，每一个节点是什么时候进栈，然后什么时候再出栈。

下面是的几个关于Binary Tree Depth例子可以很好的了解宏观思维以及微观思维

题目1: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

思路分析：这道题通过宏观思维的方式来考虑：

递归函数定义：递归函数要做的事情是找到当前节点的maxDepth，输入是当前节点，输出（返回值）是这个节点的maxDepth

递归函数拆解：当前节点的maxDepth是如何通过它的左子树的maxDepth和右子树的maxDepth得到的？如果已经知道了当前节点的左，右子树的maxDepth，那么从这两个中选出那个最大的然后加上1就得到了当前节点的maxDepth

递归函数退出条件：什么时候可以不用递归而直接得到结果呢？那就是当root为null的时候可以直接得到它的maxDepth为0

那么知道了上面的宏观思维，就可以很容易用code进行实现了：

class Solution {
    public int maxDepth(TreeNode root) {    <<<<递归函数的定义
        if (root == null) return 0;   <<<<递归函数退出条件
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;    <<<<递归函数的拆解
    }
}

题目2: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.

思路分析：这道题通过宏观思维的方式来考虑：

递归函数定义：递归函数要做的事情是判断以当前节点为根节点的tree是不是height-balanced binary tree，输入是当前节点，输出（返回值）是以此节点为根节点的tree是不是height-balanced binary tree

递归函数拆解：当前节点为根节点的tree是不是height-balance tree是如何通过它的左右子树是不是height-balanced tree来得到的呢？是由三种情况的组合得到的，左子树是不是height-balanced tree，右子树是不是height-balanced tree，以及左右子树的高度差是不是小于等于1。第三种情况可以通过辅助函数treeHeight来得到。

递归函数退出：什么时候可以不用递归而直接得到结果呢？当root为null的时候可以直接得到函数值true。

知道了上面的宏观思维，就可以很容易用code进行实现了：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(treeHeight(root.left) - treeHeight(root.right)) <=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int treeHeight(TreeNode root){
        if (root == null) return 0;
        return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
    }
}

题目3: Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree

          1
         / \
        2   3
       / \     
      4   5

Returns[4, 5, 3], [2], [1].

Explanation:

• Removing the leaves[4, 5, 3]would result in this tree:

          1
         / 
        2

• Now removing the leaf[2]would result in this tree:

          1

• Now removing the leaf[1]would result in the empty tree:

          []

Returns[4, 5, 3], [2], [1].

思路分析：这道题乍一看应该是用DFS来做，但是具体该怎么实现却不是很清晰。这道题的核心是要找到每个节点的高度，相同高度的节点放在同一个list里面，比如节点4，5，3的高度都是0，节点2的高度是1， 节点1的高度是2。

所以这道题在宏观上比较难把握，只是知道需要找到每一个节点的高度。所以这道题要理解从微观上每一个节点要如何出栈，如何入栈。首先节点要通过post order的方式进行遍历，以这道题的树为例，首先节点1入栈，然后节点2入栈，然后节点4入栈，节点4是叶子节点，其高度为1，放进高度为1的list中，然后节点4出栈，遍历到了节点2的右子树，也就是节点5，节点5也是叶子节点，高度为1，也将其放进高度为1的list中。然后节点5出栈，这个时候栈底是节点2，节点2的高度为2，将节点2放进高度为2的list中，然后节点2出栈，到达节点1的右子树，也就是节点3，节点3的高度为1，将其放到高度为1的list中，然后出栈。最后到达节点1，节点1的高度为3，故将其放到高度为3的list中。

根据上面的微观分析，可以看出一边通过post order遍历所有节点的方式找到每一个节点的高度，一边把相同高度的节点放到相应的list中。

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        treeHeight(root, result);
        return result;
    }
    public int treeHeight(TreeNode root, List<List<Integer>> result){
        if (root == null) return -1;
        int height = Math.max(treeHeight(root.left, result), treeHeight(root.right, result)) + 1;
        if (result.size() == height){
            result.add(new ArrayList<Integer>());
        }
        result.get(height).add(root.val);
        root.left = null;
        root.right = null;
        return height;
    } 
}