LeeCode Practice Journal | Day20_Binary Tree07

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

题目：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
递归的查找左右子树的条件判断更加简单了

solution：

public 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);
        else if(p.val > root.val && q.val > root.val)
            return LowestCommonAncestor(root.right, p, q);
        else
            return root;
    }
}

summary：

701.二叉搜索树中的插入操作

题目：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
递归的像子树中插入节点，并返回插入节点的子树

solution：

public class Solution {
    public TreeNode InsertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        if(val < root.val) root.left = InsertIntoBST(root.left, val);
        else root.right = InsertIntoBST(root.right, val);
        return root;
    }
}

summary：

错误：

插入节点操作只创建了新节点，没有让父节点指向新节点，忽略了回溯

450.删除二叉搜索树中的节点

题目：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
怎么样简洁的进行删除操作纠结了好一会

solution：

public class Solution {
    public TreeNode cur = null;
    public TreeNode DeleteNode(TreeNode root, int key) {
        if(root == null) return null;

        if(key < root.val) root.left = DeleteNode(root.left, key);
        else if(key > root.val) root.right = DeleteNode(root.right, key);
        else
        {
            if(root.right != null)
            {
                cur = root.right;
                while(cur.left != null) cur = cur.left;
                cur.left = root.left;
                return root.right;
            }
            else return root.left;
        }

        return root;
    }
}

summary：

key：

二叉搜索树节点的删除操作：
存在右子树时：
        删除节点的左子树成为右子树的最左节点的左子树
        删除节点的父节点指向右子树
        （顺序不可颠倒）
不存在右子树时：
        返回左子树

错误：

以为需要记录一个pre节点

删除操作的细节：
需要判断右子树是否存在

最后的return：
整个算法的逻辑用自然语言描述是若目标在节点的左子树则对左子树递归，在右子树则对右子树递归，最后返回节点，所以对左右子树操作完成后，要返回当前节点
return的本质：删除操作后的二叉树