【剑指offer】二叉树以及二叉搜索树的最近公共祖先

「爱情、让人受尽委屈。」 2021-10-03 02:26 231阅读 0赞

[面试题68 - I. 二叉搜索树的最近公共祖先][68 - I.]

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

[百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 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, 因为根据定义最近公共祖先节点可以为节点本身。

先来说明二叉搜索树的性质，其左子树上的结点都小于根结点，右子树上的结点都大于根节点。并且左右子树都是二叉搜索树

利用递归进行求解

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(p.val<root.val && q.val < root.val){
                return lowestCommonAncestor(root.left,p,q);//在左子树找
            }
            if(p.val>root.val && q.val > root.val){
                return lowestCommonAncestor(root.right,p,q);//在右子树找
            }
            return root;//如果左右子树都没有满足的公共结点，则root就是公共结点。
        }
    }

[面试题68 - II. 二叉树的最近公共祖先][68 - II.]

难度简单52

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

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

![format_png 1][]

**示例 1:**

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

**示例 2:**

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

**说明:**

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉树中。

解题思路：通过路径打印，然后在路径中找到第一个相等的值就是最近的公共祖先了。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public static boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
            if(root == null)
                return false;
            stack.push(root);    
            if(root == node)
                return true;
            if(getPath(root.left,node,stack))
                return true;
            if(getPath(root.right,node,stack))
                return true;
            stack.pop();//当前结点既不是node结点，而且他的左右子树也没有这个结点，所以这个结点不在node的路径上，所以就从栈中删除当前结点。
            return false;                
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            getPath(root,p,stack1);
            getPath(root,q,stack2);
            while(stack1.size() != stack2.size()){
                if(stack1.size()>stack2.size()){
                    stack1.pop();
                }else{
                    stack2.pop();
                }
            }
            while(stack1.size() != 0){
                if(stack2.peek() == stack1.peek()){
                    break;
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }
            return stack1.peek();
        }
    }

[68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[format_png]: /images/20211003/7409490f9e3240beaf6d52daa15a161e.png
[68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[format_png 1]: /images/20211003/d984a0b8de194481887b8c81a53237ea.png