題目

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節點 5 和節點 4 的最近公共祖先是節點 5。因為根據定義最近公共祖先節點可以為節點本身。

說明:

所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉樹中。

思路

首先，需要會：返回二叉樹中根節點到任意節點的路徑。
調用兩次該函數，返回p節點和q節點的路徑。這里的根節點到任意節點的路徑代碼思路：筆者的另一篇博客

其次，遍歷兩個路徑數組。因為都是從根節點開始的，所以順序遍歷到相同的值，則是公共祖先。

再次，最近公共祖先，是距離根節點最遠的公共祖先，隨著循環變量i的增加，不斷更新公共祖先，這樣得到的就是最遠的公共祖先。

leetcode提交

/*** 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:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*>path;//遍歷時候的臨時棧 vector<TreeNode*> node_p_path;//p結點路徑 vector<TreeNode*> node_q_path; //q結點路徑 int finish=0;pre_order(root,p,path,node_p_path,finish);//找到p節點路徑 ,存于node_p_path path.clear();//清空 finish=0; //清空 pre_order(root,q,path,node_q_path,finish);//找到q節點路徑，存于node_q_path int path_len=0;//較短路徑的長度if(node_p_path.size()<node_q_path.size())path_len=node_p_path.size();elsepath_len=node_q_path.size();TreeNode *result=0;for(int i=0;i<path_len;++i){if(node_p_path[i]==node_q_path[i])//相同節點 result=node_p_path[i];//相同則更新，直到距離根節點最遠 }return result; }//前序遍歷，找到某一結點的路徑resultvoid pre_order(TreeNode * node,TreeNode *search,vector<TreeNode*> &path, vector<TreeNode*> &result,//返回路徑結果 int &finish){if(!node||finish==1)//為空或者找到則返回 return;path.push_back(node);//保存節點數值if(node==search){finish=1;result=path;//找到則節點路徑保存 } pre_order(node->left,search,path,result,finish);pre_order(node->right,search,path,result,finish);path.pop_back();//結束遍歷node時，node節點彈出path棧 } };

測試代碼

#include<iostream>#include<vector>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){} };class solution{public:TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode *p,TreeNode *q){vector<TreeNode*>path;//遍歷時候的臨時棧 vector<TreeNode*> node_p_path;//p結點路徑 vector<TreeNode*> node_q_path; //q結點路徑 int finish=0;pre_order(root,p,path,node_p_path,finish);//找到p節點路徑 ,存于node_p_path path.clear();//清空 finish=0; //清空 pre_order(root,q,path,node_q_path,finish);//找到q節點路徑，存于node_q_path int path_len=0;//較短路徑的長度if(node_p_path.size()<node_q_path.size())path_len=node_p_path.size();elsepath_len=node_q_path.size();TreeNode *result=0;for(int i=0;i<path_len;++i){if(node_p_path[i]==node_q_path[i])//相同節點 result=node_p_path[i];//相同則更新，直到距離根節點最遠 }return result; }void pre_order(TreeNode * node,TreeNode *search,vector<TreeNode*> &path, vector<TreeNode*> &result,//返回路徑結果 int &finish){if(!node||finish==1)//為空或者找到則返回 return;path.push_back(node);//保存節點數值if(node==search){finish=1;result=path;//找到則節點路徑保存 } pre_order(node->left,search,path,result,finish);pre_order(node->right,search,path,result,finish);path.pop_back();//結束遍歷node時，node節點彈出path棧 }};int main(){//暴力構造樹TreeNode a(3);TreeNode b(5);TreeNode c(1);TreeNode d(6);TreeNode e(2);TreeNode f(0);TreeNode g(8);TreeNode h(7);TreeNode i(4);a.left=&b;//連接節點a.right=&c;c.left=&f;c.right=&g;b.left=&d;b.right=&e;e.left=&h;e.right=&i;solution solve;TreeNode *result=solve.lowestCommonAncestor(&a,&d,&i) ;cout<<"the Lowest Common Ancestor: "<<result->val<<endl; result=solve.lowestCommonAncestor(&a,&h,&i) ;cout<<"the Lowest Common Ancestor: "<<result->val<<endl; result=solve.lowestCommonAncestor(&a,&d,&g) ;cout<<"the Lowest Common Ancestor: "<<result->val<<endl; return 0;}

測試結果

題目來源：力扣（LeetCode）
鏈接：請點擊https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

總結

以上是生活随笔為你收集整理的Leetcode236 最近公共祖先-二叉树两次遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

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