#|二叉树中两个节点的最近公共祖先（leetcode） #|各种二叉树

leetcode题目地址 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description
二叉树构造

TreeNode* t1 = new TreeNode(3); TreeNode* t2 = new TreeNode(5); TreeNode* t3 = new TreeNode(1); TreeNode* t4 = new TreeNode(6); TreeNode* t5 = new TreeNode(2); TreeNode* t6 = new TreeNode(0); TreeNode* t7 = new TreeNode(8); TreeNode* t8 = new TreeNode(7); TreeNode* t9 = new TreeNode(4); t1->left = t2; t1->right = t3; t2->left = t4; t2->right = t5; t3->left = t6; t3->right = t7; t5->left = t8; t5->right = t9; TreeNode* root = t1; /* _______3______ /\ ___5_____1__ /\/\ 6_208 /\ 74 */

AC1 使用dfs得到根结点到某个结点的路径，然后比对路径就可以得到最近的公共祖先

/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public:vector fa1; vector fa2; void dfs(vector &fa, TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return ; if (root == p){ fa1 = fa; } if (root == q){ fa2 = fa; }if (root->left != NULL){ fa.push_back(root->left); dfs(fa,root->left, p,q); fa.pop_back(); } if (root->right != NULL) { fa.push_back(root->right); dfs(fa, root->right, p,q); fa.pop_back(); } }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector fa; fa.push_back(root); dfs(fa, root, p,q); vector::iterator it1 = fa1.begin(); vector::iterator it2 = fa2.begin(); TreeNode* ans = NULL; ; while (it1 != fa1.end() && it2 != fa2.end()) { if (*it1 == *it2) { ans = *it1; it1++; it2++; } else{ break; } }return ans; } };

ac2 参考思路：
http://blog.csdn.net/shixiaoguo90/article/details/23824325
遍历二叉树时，只有先访问给定两节点A、B后，才可能确定其最近共同父节点C，因而采用后序遍历。
可以统计任一节点的左右子树“是否包含A、B中的某一个”（也可以直接统计“包含了几个A、B”）。当后序遍历访问到某个节点D时，可得到三条信息：（1）节点D是否是A、B两节点之一、（2）其左子树是否包含A、B两节点之一、（3）其右子树是否包含A、B两节点之一。当三条信息中有两个为真时，就可以确定节点D的父节点（或节点D，如果允许一个节点是自身的父节点的话）就是节点A、B的最近共同父节点。另外，找到最近共同父节点C后应停止遍历其它节点。
【#|二叉树中两个节点的最近公共祖先（leetcode）】原文的代码似乎不符合，我重新改写了一下代码，ac如下：

/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public:bool lca(TreeNode *root, TreeNode* va, TreeNode* vb, TreeNode *&result) { // left/right 左/右子树是否含有要判断的两节点之一 bool left = false, right = false; if (!result && root->left != NULL) left = lca(root->left,va,vb,result); if (!result && root->right != NULL) right = lca(root->right,va,vb,result); // mid 当前节点是否是要判断的两节点之一 bool mid = false; if (root == va || root == vb) mid = true; if (!result && int(left + right + mid) == 2) { result = root; // root就是后序遍历（左，右，根），当前遍历的那个节点 } return left | mid | right ; }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; TreeNode *result = NULL; lca(root, p, q,result); return result; } };