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

左手的ㄟ右手 2022-09-14 14:27 148阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、题解
     *  三、二叉树解法
     *  四、二叉搜索树解法
     *  五、迭代法
     *  六、总结

## 一、题目 ##

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、题解 ##

该题可以直接按照：[ 二叉树的最近公共祖先][Link 1]

的思路去解决

但是本题已经说明是二叉搜索树，所以需要从二叉搜索树的特性去考虑

所以可以采用 **前序遍历** 的思想

遍历的过程中，如果根节点在两节点之间，则说明该节点即为最近公共祖先

## 三、二叉树解法 ##

具体思路可参考：[ 二叉树的最近公共祖先][Link 1]

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == p || root == q || root == null) { 
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) { 
                return root;
            }
            if (left == null) { 
                return right;
            }
            return left;
        }
    }

## 四、二叉搜索树解法 ##

（1）确定递归函数返回值及参数

lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

（2）确定递归终止条件

> 二叉树遍历常用递归终止条件：遇到空节点返回即可

if (root == null) { 
    	return root;
    }

（3）确定单层递归的逻辑

> 由于是先序遍历，所以当找到根节点的值属于 `[p.val,q.val]` 的区间即可  
> 注意这里是左闭右闭的区间  
> 同时由于这里不知道 p 和 q 谁大，所以两个都需要判断

//向左遍历的情况
            if (root.val > p.val && root.val > q.val) { 
                TreeNode left = lowestCommonAncestor(root.left, p, q);
                if (left != null) { 
                    return left;
                }
            }
            //向右遍历的情况
            if (root.val < p.val && root.val < q.val) { 
                TreeNode right = lowestCommonAncestor(root.right, p, q);
                if (right != null) { 
                    return right;
                }
            }

**这里是搜索的是一条边，不需要搜索整个树**

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null) { 
                return root;
            }
            //向左遍历的情况
            if (root.val > p.val && root.val > q.val) { 
                TreeNode left = lowestCommonAncestor(root.left, p, q);
                if (left != null) { 
                    return left;
                }
            }
            //向右遍历的情况
            if (root.val < p.val && root.val < q.val) { 
                TreeNode right = lowestCommonAncestor(root.right, p, q);
                if (right != null) { 
                    return right;
                }
            }
            return root;
        }
    }

精简版：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            //因为题目已经说明 p 和 q 均存在于二叉搜索树中，所以不需要判断 root 节点空的情况
            if (root.val > p.val && root.val > q.val) { 
                return lowestCommonAncestor(root.left, p, q);
            }else if (root.val < p.val && root.val < q.val) { 
                return lowestCommonAncestor(root.right, p, q);
            }else { 
                return root;
            }
        }
    }

## 五、迭代法 ##

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            while (root != null) { 
                if (root.val > p.val && root.val > q.val) { 
                    root = root.left;
                } else if (root.val < q.val && root.val < p.val) { 
                    root = root.right;
                } else { 
                    return root;
                }
            }
            return null;
        }
    }

## 六、总结 ##

**搜索一条边的写法：**

if (递归函数(root->left)) return ;
    if (递归函数(root->right)) return ;

**搜索整个树的写法：**

left = 递归函数(root->left);
    right = 递归函数(root->right);
    left与right的逻辑处理;

--------------------

**该题重在利用二叉搜索树的特性，采用先序遍历去处理**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20220828/e24f9b2052574c3f954d5f53230da0b7.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/116595804