綏化市建設(shè)局網(wǎng)站app推廣平臺放單平臺
二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為:“對于有根樹 T 的兩個節(jié)點 p、q,最近公共祖先表示為一個節(jié)點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節(jié)點也可以是它自己的祖先)?!?/p>
示例 1:
輸入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出:3
解釋:節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3 。
示例 2:
輸入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出:5
解釋:節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5 。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。
示例 3:
輸入:root = [1,2], p = 1, q = 2
輸出:1
提示:
樹中節(jié)點數(shù)目在范圍 [2, 105] 內(nèi)。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于給定的二叉樹中。
思路
后序遍歷,父節(jié)點會接收到子節(jié)點問否是p,q,并把這個狀態(tài)向上傳遞,直到滿足條件
- 返回值 節(jié)點
- 參數(shù) 輸入節(jié)點,p,q
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
- 終止條件
節(jié)點==p 或 ==q 或 為空
if(root==p || root==q || root== NULL) return root;
- 單次遞歸
采用后序,左右中,
左操作:設(shè)立參數(shù)left接收左子樹是否有p,q,有的話left為p或q
右操作:設(shè)立參數(shù)right接收右子樹是否有p,q,有的話right為p或q
TreeNode* left=lowestCommonAncestor(root->left,p,q);TreeNode* right=lowestCommonAncestor(root->right,p,q);
中操作:將本遞歸返回的參數(shù)進(jìn)行判斷,
左有q,右有p
左有p,右有q
上面一條成立,則此中節(jié)點為父節(jié)點
if(left==NULL && right!=NULL) return right;if(left!=NULL && right==NULL) return left;if(left!=NULL && right!=NULL) return root;return NULL;
left和right的取值是靠終止條件返回,沒找到p或q,left和right就會一直是NULL
if(root==p || root==q || root== NULL) return root;