這個問題可以分為三種情況來考慮：
情況一：root未知，但是每個節點都有parent指針
此時可以分別從兩個節點開始，沿著parent指針走向根節點，得到兩個鏈表，然后求兩個鏈表的第一個公共節點，這個方法很簡單，不需要詳細解釋的。

情況二：節點只有左、右指針，沒有parent指針，root已知
思路：有兩種情況，一是要找的這兩個節點（a, b），在要遍歷的節點（root）的兩側，那么這個節點就是這兩個節點的最近公共父節點；
二是兩個節點在同一側，則 root->left 或者 root->right 為 NULL，另一邊返回a或者b。那么另一邊返回的就是他們的最小公共父節點。
遞歸有兩個出口，一是沒有找到a或者b，則返回NULL；二是只要碰到a或者b，就立刻返回。
// 二叉樹結點的描述 typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; // 左右孩子 }BinaryTreeNode; // 節點只有左指針、右指針，沒有parent指針，root已知 BinaryTreeNode* findLowestCommonAncestor(BinaryTreeNode* root , BinaryTreeNode* a , BinaryTreeNode* b) {if(root == NULL)return NULL;if(root == a || root == b)return root;BinaryTreeNode* left = findLowestCommonAncestor(root->lchild , a , b);BinaryTreeNode* right = findLowestCommonAncestor(root->rchild , a , b);if(left && right)return root;return left ? left : right; }
情況三： 二叉樹是個二叉查找樹，且root和兩個節點的值(a, b)已知
// 二叉樹是個二叉查找樹，且root和兩個節點的值(a, b)已知 BinaryTreeNode* findLowestCommonAncestor(BinaryTreeNode* root , BinaryTreeNode* a , BinaryTreeNode* b) {char min , max;if(a->data < b->data)min = a->data , max = b->data;elsemin = b->data , max = a->data;while(root){if(root->data >= min && root->data <= max)return root;else if(root->data < min && root->data < max)root = root->rchild;elseroot = root->lchild;}return NULL; }

總結

以上是生活随笔為你收集整理的程序员面试100题之十六：二叉树中两个节点的最近公共父节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。