题解 | #二叉搜索树的最近公共祖先#

二叉搜索树的最近公共祖先

http://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f

题目的主要信息：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先：

对于该题的最近的公共祖先定义：对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大
一个节点也可以是它自己的祖先
二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
所有节点的值都是唯一的，可以通过节点值直接比较
p、q 为不同节点且均存在于给定的二叉搜索树中

举一反三：

学习完本题的思路你可以解决如下题目：

BM30. 二叉搜索树与双向链表

BM38. 在二叉树中找到两个节点的最近公共祖先

方法一：搜索路径比较（推荐使用）

知识点：二叉搜索树

二叉搜索树是一种特殊的二叉树，它的每个节点值大于它的左子节点，且大于全部左子树的节点值，小于它右子节点，且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。

思路：

二叉搜索树没有相同值的节点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q：

//节点值都不同，可以直接用值比较
while(node.val != target) { 
    path.add(node.val);
    //小的在左子树
    if(target < node.val) 
        node = node.left;
    //大的在右子树
    else 
        node = node.right;
}

直接得到从根节点到两个目标节点的路径，这样我们利用路径比较就可以找到最近公共祖先。

具体做法：

step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，直到找到目标节点。这个过程成用数组记录遇到的元素。
step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。
step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    //求得根节点到目标节点的路径
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        //节点值都不同，可以直接用值比较
        while(node.val != target){ 
            path.add(node.val);
            //小的在左子树
            if(target < node.val) 
                node = node.left;
            //大的在右子树
            else 
                node = node.right;
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPath(root, p); 
        ArrayList<Integer> path_q = getPath(root, q);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){ 
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if(x == y) 
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    //求得根节点到目标节点的路径
    vector<int> getPath(TreeNode* root, int target) {
        vector<int> path;
        TreeNode* node = root;
        //节点值都不同，可以直接用值比较
        while(node->val != target){ 
            path.push_back(node->val);
            //小的在左子树
            if(target < node->val) 
                node = node->left;
            //大的在右子树
            else 
                node = node->right;
        }
        path.push_back(node->val);
        return path;
    }
    
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        //求根节点到两个节点的路径
        vector<int> path_p = getPath(root, p); 
        vector<int> path_q = getPath(root, q);
        int res;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){ 
            if(path_p[i] == path_q[i])
                //最后一个相同的节点就是最近公共祖先
                res = path_p[i]; 
            else
                break;
        }
        return res;
    }
};

Python实现代码

class Solution:
    def getPath(self, root: TreeNode, target: int) -> List[int]:
        path = []
        node = root
        # 节点值都不同，可以直接用值比较
        while node.val != target: 
            path.append(node.val)
            # 小的在左子树
            if target < node.val: 
                node = node.left
            # 大的在右子树
            else: 
                node = node.right
        path.append(node.val)
        return path
    
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # 求根节点到两个节点的路径
        path_p = self.getPath(root, p) 
        path_q = self.getPath(root, q)
        # 比较两个路径，找到第一个不同的点
        i = 0
        while i < len(path_p) and i < len(path_q):
            if path_p[i] == path_q[i]:
                # 最后一个相同的节点就是最近公共祖先
                res = path_p[i]; 
                i += 1
            else:
                break
        return res

复杂度分析：

时间复杂度： $O (n)$ ，设二叉树共有 $n$ 个节点，因此最坏情况二叉搜索树变成链表，搜索到目标节点需要 $O (n)$ ，比较路径前半段的相同也需要 $O (n)$
空间复杂度： $O (n)$ ，记录路径的数组最长为 $n$

方法二：一次遍历（扩展思路）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。