Problem: 236. 二叉樹的最近公共祖先

題目描述

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

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

思路

首先我們要注意到題目所給提示**二叉樹的所有節點值均不相等！！！**在此基礎上我們可以得到二叉樹的最近公共祖先的唯一存在如下兩種情況：

1.若當前節點的左子樹和右子樹均存在給定節點的其一，則當前節點為最近公共祖先；
2.若當前節點等于所給節點的其中一個，同時當前節點的左子樹或者右子樹中存在所給節點的另一個節點，則當前節點為最近公共祖先

如下圖示：

解題方法

1.定義一個TreeNode類型的指針命名為location用于記錄并返回最后的最近公共祖先
2.遞歸后續遍歷二叉樹，記錄當前節點（包括當前節點）的左子樹或右子樹節點等于給定節點的個數
3.判斷當前節點是否等于給定節點中其一，同時其左右子樹中等于給定節點的個數（具體的判定條件看思路）判定成立時將指針location指向當前節點。
4.注意若在遞歸過程中發現指針location已經不為null則直接退出遞歸

復雜度

時間復雜度:

$O(n)$

空間復雜度:

$O(n)$

Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {//用于記錄指定節點最近的父節點位置private TreeNode location = null;/*** 求取二叉樹中指定兩節點的最近公共父節點（二叉樹任意節點值無重復）** @param root 樹的根節點* @param p    指定節點p* @param q    指定節點q* @return TreeNode*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {depthFirstSearch(root, p, q);return location;}/*** 深度優先（此處為二叉樹的后序遍歷）求取某一節點指定的* 節點p 與 q的個數，利用其找到最近父節點的位置* @param root 樹的根節點* @param p    指定節點p* @param q    指定節點q* @return int*/private int depthFirstSearch(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return 0;}//當前節點左子樹包含p，q節點的個數int leftContains = depthFirstSearch(root.left, p, q);//當已經找到location時提前退出if (location != null) {return 2;}//當前節點右子樹包含p，q節點的個數int rightContains = depthFirstSearch(root.right, p, q);if (location != null) {return 2;}//記錄當前節點值等于q或pint rootContain = 0;//如果當前節點值等于p，q其一if (root == p || root == q) {rootContain = 1;}/*找到情況1：當當前節點值等于p，q其一時，同時當前節點的左子樹或右子樹包含q，p的個數為1找到情況2：當當前節點的左子樹包含一個p或q其一，同時當前節點的右子樹包含一個q或p其一*/if (rootContain == 1 && (leftContains == 1 || rightContains == 1)) {location = root;}if (rootContain == 0 && leftContains == 1 && rightContains == 1) {location = root;}return leftContains + rightContains + rootContain;}
}