[数据结构与算法]力扣算法学习day17-3

力扣算法学习day17-3

450-删除二叉搜索树中的结点

题目

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){// 1.没有找到
            return null;
        }

        if(key == root.val){// 2.找到了
            if(root.left == null && root.right == null){// 找到的结点为叶子结点
                return null;
            }

            if(root.left == null){// 找到结点左节点为空，右节点不为空。
                return root.right;
            }

            if(root.right == null){// 找到结点右节点为空，左节点不为空
                return root.left;
            }

            // 上面都没有进入，则找到的结点左右结点都不为空。
            TreeNode temp = root.right;
            while(temp.left != null){
                temp = temp.left;
            }
            temp.left = root.left;
            return root.right;
        }

        // 当前结点不等于，继续按照规则查找
        if(key < root.val){
            root.left = deleteNode(root.left,key);
        }else{
            root.right = deleteNode(root.right,key);
        }

        return root;
    }
}