1. 二叉树的节点个数的范围是 [1,104]
2. -231 <= Node.val <= 231 - 1

因为我们先遍历左子树，然后再遍历右子树，所以对同一高度的所有节点，最左节点肯定是最先被遍历到的。

1. public int findBottomLeftValue(TreeNode root) {
2.     int curHeight = 0;
3.     dfs(root, 0);
4. return curVal;
5. }
6. 
7. public void dfs(TreeNode root, int height) {
8. if (root == null) {
9. return;
10.     }
11.     height++;
12.     dfs(root.left, height);
13.     dfs(root.right, height);
14. if (height > curHeight) {
15.         curHeight = height;
16.         curVal = root.val;
17.     }
18. }

1. 树中节点的数目在范围 [0, 5000] 内
2. -1000 <= Node.val <= 1000
3. -1000 <= targetSum <= 1000

1. 1 <= inorder.length <= 3000
2. postorder.length == inorder.length
3. -3000 <= inorder[i], postorder[i] <= 3000
4. inorder 和 postorder 都由 不同 的值组成
5. postorder 中每一个值都在 inorder 中
6. inorder 保证是树的中序遍历
7. postorder 保证是树的后序遍历

1. 如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子。
2. 如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子。

1. uu 是 vv 的右儿子。这是因为在遍历到 uu 之后，下一个遍历的节点就是 uu 的双亲节点，即 vv；
2. 
3. vv 没有右儿子，并且 uu 是 vv 的某个祖先节点(或者 vv 本身)的左儿子。如果 vv 没有右儿子，那么上一个遍历的节点就是 vv 的左儿子。如果 vv 没有左儿子，则从 vv 开始向上遍历 vv 的祖先节点，直到遇到一个有左儿子(且 vv 不在它的左儿子的子树中)的节点 vava，那么 uu 就是 vava 的左儿子。

1. 3
2. / \
3. 9  20
4. / \   \
5. 15 10   7
6. / \
7. 5   8
8.            \
9. 4

1. 我们遍历 20。20 一定是栈顶节点 3 的右儿子。我们使用反证法，假设 20 是 3 的左儿子，因为 20 和 3 中间不存在其他的节点，那么 3 没有右儿子，index 应该恰好指向 3，但实际上为 4，因此产生了矛盾。所以我们将 20 作为 3 的右儿子，并将 20 入栈。
2.     stack = [3, 20]
3. index -> inorder[8] = 4
4. 
5. 我们遍历 7，8 和 4。同理可得它们都是上一个节点(栈顶节点)的右儿子，所以它们会依次入栈。
6.     stack = [3, 20, 7, 8, 4]
7. index -> inorder[8] = 4
8. 
9. 我们遍历 5，这时情况就不一样了。我们发现 index 恰好指向当前的栈顶节点 4，也就是说 4 没有右儿子，那么 5 必须为栈中某个节点的左儿子。那么如何找到这个节点呢？栈中的节点的顺序和它们在反向前序遍历中出现的顺序是一致的，而且每一个节点的左儿子都还没有被遍历过，那么这些节点的顺序和它们在反向中序遍历中出现的顺序一定是相反的。
10. 
11.     这是因为栈中的任意两个相邻的节点，前者都是后者的某个祖先。并且我们知道，栈中的任意一个节点的左儿子还没有被遍历过，说明后者一定是前者右儿子的子树中的节点，那么后者就先于前者出现在反向中序遍历中。
12. 
13. 因此我们可以把 index 不断向左移动，并与栈顶节点进行比较。如果 index 对应的元素恰好等于栈顶节点，那么说明我们在反向中序遍历中找到了栈顶节点，所以将 index 减少 1 并弹出栈顶节点，直到 index 对应的元素不等于栈顶节点。按照这样的过程，我们弹出的最后一个节点 x 就是 5 的双亲节点，这是因为 5 出现在了 x 与 x 在栈中的下一个节点的反向中序遍历之间，因此 5 就是 x 的左儿子。
14. 
15. 回到我们的例子，我们会依次从栈顶弹出 4，8 和 7，并且将 index 向左移动了三次。我们将 5 作为最后弹出的节点 7 的左儿子，并将 5 入栈。
16.     stack = [3, 20, 5]
17. index -> inorder[5] = 5
18. 
19. 我们遍历 9。同理，index 恰好指向当前栈顶节点 5，那么我们会依次从栈顶弹出 5，20 和 3，并且将 index 向左移动了三次。我们将 9 作为最后弹出的节点 3 的左儿子，并将 9 入栈。
20.     stack = [9]
21. index -> inorder[2] = 10
22. 
23. 我们遍历 10，将 10 作为栈顶节点 9 的右儿子，并将 10 入栈。
24.     stack = [9, 10]
25. index -> inorder[2] = 10
26. 
27. 我们遍历 15。index 恰好指向当前栈顶节点 10，那么我们会依次从栈顶弹出 10 和 9，并且将 index 向左移动了两次。我们将 15 作为最后弹出的节点 9 的左儿子，并将 15 入栈。
28.     stack = [15]
29. index -> inorder[0] = 15

1. 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点(后序遍历的最后一个节点)，指针指向中序遍历的最后一个节点；
2. 
3. 我们依次枚举后序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向左移动 index，并将当前节点作为最后一个弹出的节点的左儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的右儿子；
4. 
5. 无论是哪一种情况，我们最后都将当前的节点入栈。