剑指offer 面试题68(java版):二叉搜索树的最近公共祖先

傷城~ 2023-07-08 09:13 27阅读 0赞

### [welcome to my blog][] ###

## 剑指offer面试题68(java版):二叉搜索树的最近公共祖先 ##

### 题目描述 ###

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
    满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    
    例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

![format_png][]

示例 1:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    示例 2:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

####  ####

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

#### 第一次做; 循环版, 考虑BST的性质 ####

class Solution { 
        /* LCA: 要么在root的左子树中, 要么在root的右子树中, 要么是root */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root==null)
                return null;
            //
            while(root!=null){ 
                if(p.val > root.val && q.val > root.val)
                    root = root.right;
                else if(p.val < root.val && q.val < root.val)
                    root = root.left;
                else
                    break;
            }
            return root;
        }
    }

#### 第一次做; 递归版; 考虑BST的性质: root左子树中的值都比root.val小, root右子树中的值都比root.val大 ####

class Solution { 
        /* LCA: 要么在root的左子树中, 要么在root的右子树中, 要么是root */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root==null)
                return null;
            //
            if(p.val>root.val && q.val>root.val){ 
                return lowestCommonAncestor(root.right, p, q);
            }
            else if(p.val<root.val && q.val<root.val){ 
                return lowestCommonAncestor(root.left, p, q);
            }
            else{ 
                return root;
            }
        }
    }

#### 第一次做; 不考虑BST的性质; 直接使用递归解决: LCA要么在root的左子树中, 要么在root的右子树中, 要么就是root ####

class Solution { 
        /* LCA: 要么在root的左子树中, 要么在root的右子树中, 要么是root */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root==null || root==p || root ==q)
                return root;
            TreeNode leftRes = lowestCommonAncestor(root.left, p, q);
            TreeNode rightRes = lowestCommonAncestor(root.right, p, q);
            if(leftRes!=null && rightRes!=null)
                return root;
            return leftRes==null?rightRes:leftRes;
        }
    }

#### [力扣题解][Link 1] 循环的方式记录路径 ####

如题目中的图所示
    若p是节点5， q是节点4
    root 到 p 的路径 3 5
    root 到 q 的路径 3 5 2 4

class Solution {
    public:
        void getPath(TreeNode *root, TreeNode *end, vector<TreeNode*>& path) {
            stack<TreeNode*> stk;
            TreeNode *p = root, *prev = nullptr;
            while (p || !stk.empty()) {
                while (p) {
                    stk.push(p);
                    path.push_back(p);
                    if (p == end) return;
                    p = p->left;
                }
                p = stk.top();
                if (!p->right || p->right == prev) {
                    path.pop_back();
                    stk.pop();
                    prev = p;
                    p = nullptr;
                } else {
                    p = p->right;
                }
            }
        }
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> path1, path2;
            getPath(root, p, path1);
            getPath(root, q, path2);
            int n = min(path1.size(), path2.size());
            TreeNode *last = nullptr;
            for (int i = 0; i < n; i++) {
                if (path1[i] != path2[i]) return last;
                last = path1[i];
            }
            return last;
        }
    };

[welcome to my blog]: https://littlehaes.com
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS83MGJiYmYxYzNmZTRkYzVkN2Y1MWU0MDMyOTI2ODhiMC94bWxub3RlLzA3QjgzQzAwODhFODRDRDFBRjI5NERDMzQwQTEzRTFFLzYzMDM2?x-oss-process=image/format,png
[Link 1]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/shuang-100fei-di-gui-di-gui-shi-xian-by-happy_yuxu/