其实就是post-order traversal

有2道题可以用到这个技巧

1 Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

2

### 判断二叉树是不是平衡

http://zhedahht.blog.163.com/blog/static/25411174201142733927831/

http://www.geeksforgeeks.org/check-given-binary-tree-follows-height-property-red-black-tree/

3.

http://leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

Naive Approach:

A naive approach is to reuse the solution from Determine if a Binary Tree is a Binary Search Tree. Starting from the root, we process in the order of current node, left child, then right child. For each node, you would call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then we have to continue examining its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.

Assume that we have a complete tree (ie, all leaves are at the same depth) with n nodes, the naive approach’s run time complexity is O(n lg n). The proof is left as an exercise to the reade

**A Bottom-up Approach:**

The naive approach is using a top-down approach. It is hardly efficient, simply because we are calling *isBST()* over and over again. Each time *isBST()* is called, it traverses down to the leaves to verify if the subtree is a BST.

lca为什么是post order？ root先被访问吧????