提示：

樹中節(jié)點(diǎn)數(shù)目在范圍 [2, 105] 內(nèi)。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于給定的二叉樹中

思路一：如果給定的是一顆二叉搜索樹，

二叉搜索樹：中序遍歷的大小是有序的，根節(jié)點(diǎn)的左樹都比根節(jié)點(diǎn)的小，根節(jié)點(diǎn)的右樹都比根節(jié)點(diǎn)大。

?

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //先根據(jù)二叉搜索樹來寫
        if(root==null) return null;
        if(root==p||root==q) return root;
        TreeNode leftT=lowestCommonAncestor(root.left,p,q);
        TreeNode rightT=lowestCommonAncestor(root.right,p,q);
        if(leftT!=null&&rightT!=null){
            return root;
        }else if(leftT!=null){
            return leftT;
        }else{
            return rightT;

        }
        
    }
}

思路二：假設(shè)是孩子雙親表示法

就相當(dāng)于鏈表求交點(diǎn)，但是我們的表示中沒有雙親結(jié)點(diǎn)，因此我們引入兩個(gè)棧。

1.用兩個(gè)棧 存儲(chǔ)root->q,root->p的路徑；

2.求棧的大??；

3.讓棧中多的元素出差值個(gè)元素；

4.開始出棧，直到棧頂元素相同，就是公共祖先；

如何去找到從根節(jié)點(diǎn)到一個(gè)指定節(jié)點(diǎn)的路徑？?文章來源地址http://www.zghlxwxcb.cn/news/detail-402102.html

class Solution {
    //root根結(jié)點(diǎn)，node:指定的節(jié)點(diǎn)，stack:存放根節(jié)點(diǎn)到指定節(jié)點(diǎn)的路徑
    public boolean getPath(TreeNode root,TreeNode node ,Stack<TreeNode> stack){
        if(root==null||node==null) return false;
        stack.push(root);
        if(node==root) return true;
        boolean flg=getPath(root.left,node,stack);
        if(flg==true) return true;//找到啦
      flg=getPath(root.right,node,stack);
        if(flg==true) return true;//找到啦
        stack.pop();
        return false;

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        Stack<TreeNode> stack1=new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2){
            int size=size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                //直接判斷地址
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }

        }else{
            int size=size2-size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
            while(!stack1.isEmpty()&&!stack2.isEmpty()){
                //直接判斷地址
                if(stack1.peek()==stack2.peek()){
                    return stack2.pop();
                }else{
                    stack1.pop();
                    stack2.pop();
                }
            }
        }
        return null;



    }
}

?二叉搜索樹

是空樹或者：

若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值

若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值

它的左右子樹也分別為二叉搜索樹

定義Node類

class Node{
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val=val;
    }
}

查找

  public Node root=null;
    public Node search(int key){
        Node cur = root;
        if(cur.val<key){
            cur = cur.right;
        }else if(cur.val>key){
            cur = cur.left;
        }else{
            return cur;
        }
        return null;
    }

刪除

設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 parent

1. cur.left == null

1. cur 是 root ，則 root = cur.right

2. cur 不是 root ， cur 是 parent.left ，則 parent.left = cur.right

3. cur 不是 root ， cur 是 parent.right ，則 parent.right = cur.right

2. cur.right == null

1. cur 是 root ，則 root = cur.left

2. cur 不是 root ， cur 是 parent.left ，則 parent.left = cur.left

3. cur 不是 root ， cur 是 parent.right ，則 parent.right = cur.left

3. cur.left != null && cur.right != null

1. 需要使用 替換法 進(jìn)行刪除，即在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn) ( 關(guān)鍵碼最小 ) ，用它的值填補(bǔ)到被

刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題

   //要?jiǎng)h除節(jié)點(diǎn)，你需要知道這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
    //當(dāng)要?jiǎng)h除的節(jié)點(diǎn)的左節(jié)點(diǎn)為空
    //一般刪除節(jié)點(diǎn)都是刪除葉子節(jié)點(diǎn)

    public void f(Node cur,Node parent){
        if(cur.left==null){//當(dāng)刪除的節(jié)點(diǎn)左邊沒有節(jié)點(diǎn)
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;

            }else{
                parent.right=cur.right;

            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{//左右節(jié)點(diǎn)都不是空
            //相當(dāng)于在右樹中找一個(gè)較小值換到那個(gè)位置
            //或者就是在左樹中找較大值
            //
            Node targetParent=cur;
            Node target=cur.right;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            cur.val=target.val;
            if(target==targetParent.left){
                targetParent.left=target.right;
            }else{
                targetParent.right=target.right;
            }
        }


    }
    public void remove(int key){
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val==key){
                f(cur,parent);
                break;
            }else if(cur.val<key){
                parent=cur;
                cur=cur.right;
            }else{
                parent=cur;
                cur=cur.left;
            }

        }
    }

插入

   //二叉搜索樹插入的數(shù)據(jù)一定是在葉子節(jié)點(diǎn)
    //1.cur,parent來找到val需要存儲(chǔ)的位置
    //2.parent.val比較大小，確定格式在左邊還是右邊進(jìn)行插入
    public  boolean insert(int val){
        if(root == null){
            root = new Node(val);
            return true;

        }
        Node cur = root;
        Node parent = null;
        //找到parent的位置
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){//bu
                return false;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
        //找到對(duì)應(yīng)位置開始插入
        Node node=new Node(val);
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        return true;

    }

到了這里，關(guān)于Java——二叉樹的最近公共祖先及二叉搜索樹介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！