LCA
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
https://leetcode.com/problems/validate-binary-search-tree/

普通二叉树：
自下向上的解法
我觉得应该再加一层，先检查p，q是不是都在树上。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root == p || root == q) return root;
        TreeNode * left = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        if(!left && right) return right;
        if(left && !right) return left;
        return NULL;
    }
};

以上方法无法在不存在的时候返回空。

自上向下的解法，平衡情况 O(n)，最坏情况O(n^2)：
但其实这个也没有检查是否是否两个节点都出现在树上。
http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-i/

// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}
 
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}    

非递归方法，注意最后路径分叉和包含问题。

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* t1, TreeNode* t2) {
        if(!root || !t1 || !t2) return NULL;
        int num = 0;
        vector<TreeNode *> st;
        TreeNode * p = root;
        TreeNode * pre = NULL;
        vector<TreeNode *> path1, path2;
        while(!st.empty() || p!=NULL) {
            if(p!=NULL) {
                st.push_back(p);
                if(p == t1) {
                    path1 = st;
                }
                if(p == t2) {
                    path2 = st;
                }
                p = p->left;
            } else {
                TreeNode * n = st.back(); 
                if(n->right != pre && n->right != NULL){
                    p = n->right;
                } else {
                    st.pop_back();
                    pre = n;
                }
            }
        }
        
        int m = min(path1.size(), path2.size());
        int i;
        for(i = 0; i < m; i++) {
            if(path1[i] != path2[i] && i > 0) {
                return path1[i-1];
            }
        }
        if(i == m) {
            return path1[i-1];
        }
        return NULL;
    }
};

BST的相似题目：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val > q->val) {
            swap(p,q);
        }
        if(root->val >= p->val && root->val <= q->val) {
            return root;
        }
        if(root->val > q->val) {
            return lowestCommonAncestor(root->left,p,q);
        }
        if(root->val < p->val) {
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

iterative:
https://leetcode.com/discuss/45511/easy-c-recursive-and-iterative-solutions

class Solution { 
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        while (true) {
            if (p -> val < cur -> val && q -> val < cur -> val)
                cur = cur -> left;
            else if (p -> val > cur -> val && q -> val > cur -> val)
                cur = cur -> right;
            else return cur; 
        }
    }
};    

把Binary Tree拉成串
Flatten Binary Tree to Linked List

class Solution {
    TreeNode * helper(TreeNode * root) {
        if(root == NULL) return NULL;
        if(!root->left && !root->right) { return root;}
        TreeNode * ltail = helper(root->left);
        TreeNode * rhead = root->right;
        if(root->left) {
            root->right = root->left;
            root->left = NULL;
            ltail->right = rhead;
        }
        TreeNode * rtail = helper(root->right);
        return rtail;
    }
public:
    void flatten(TreeNode* root) {
        if(root == NULL) return;
        helper(root);
    }
};

106.Construct Binary Tree from Inorder and Postorder Traversal

class Solution {
    TreeNode * helper(vector<int>& inorder, vector<int>& postorder, int ii, int ij, int pi, int pj) {
        if(ii > ij || pi > pj) {
            return NULL;
        }
        TreeNode * root = new TreeNode(postorder[pj]);
        int mid;
        for(int i = ii; i <= ij; i++) {
            if(inorder[i] == postorder[pj]) {
                mid = i;
                break;
            }
        }
        int leftlen = mid - ii;
        int rightlen = ij - mid;
        TreeNode * l = helper(inorder, postorder, ii, mid - 1, pi, pi+ leftlen - 1);
        TreeNode * r = helper(inorder, postorder, mid + 1, ij, pi + leftlen, pj - 1);
        root->left = l;
        root->right = r;
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        return helper(inorder,postorder, 0, n-1, 0, n-1);
    }
};

98.Validate Binary Search Tree

class Solution {
    bool helper(TreeNode * root, TreeNode * smallest, TreeNode * largest) {
        if(root == NULL) {return true;}
        if(smallest) {
            if(root->val <= smallest->val) {return false;}
        }
        if(largest) {
            if(root->val >= largest->val) {return false;}
        }
        return helper(root->left,smallest,root) && helper(root->right, root, largest);
    }
public:
    bool isValidBST(TreeNode* root) {
        return helper(root,NULL,NULL);
    }
};

inorder遍历
https://leetcode.com/discuss/14886/order-traversal-please-rely-buggy-int_max-int_min-solutions

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return validate(root, prev);
    }
    bool validate(TreeNode* node, TreeNode* &prev) {
        if (node == NULL) return true;
        if (!validate(node->left, prev)) return false;
        if (prev != NULL && prev->val >= node->val) return false;
        prev = node;
        return validate(node->right, prev);
    }
};