Day32——二叉树专题

---

28.删除二叉搜索树的节点

题目链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

• 如果目标节点大于当前节点值，则去右子树中删除；

• 如果目标节点小于当前节点值，则去左子树中删除;

• 如果目标节点就是当前节点，分为以下三种情况：

  • 其无左子：其右子顶替其位置，删除了该节点；

  • 其无右子：其左子顶替其位置，删除了该节点；

  • 其左右子都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替了其位置，并且删除该节点；

    左右子树都有的情况：

    

代码实现：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return dfs(root, key);
    }
    public TreeNode dfs(TreeNode root, int key){
        if(root == null){
            return null;
        }

        if(root.val > key) root.left = dfs(root.left, key);
        else if(root.val < key) root.right = dfs(root.right, key);
        else{// 当前节点是要删除的节点
            if(root.left == null) return root.right;// 情况1：左子树为空
            if(root.right == null) return root.left;// 情况2：右子树为空

            // 情况3：左右都不为空
            TreeNode node = root.right;
            while(node.left != null){// 找出右子树最左的节点
                node = node.left;
            }
            node.left = root.left;// 删除欲删除节点 拼接
            root = root.right;// 跟换删除后树的根节点
        }

        // 递归完整结束后 返回根节点
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

29.修剪二叉搜索树

题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）

思路：

• root的元素值为null，直接返回null

   if(root == null){
            return null;
        }
1
2
3

• root.val < low,递归右子树，并返回右子树符合条件的头节点

 if(root.val<low){
            return dfs(root.right,low,high);
        }
1
2
3

• root.val > high,递归左子树，并返回左子树符合条件的头节点

    if(root.val>high){
            return dfs(root.left,low,high);
        }
1
2
3

• 接下来将下一层处理完左子树结果赋值给root->left，右子树结果赋值给root->right。最后返回root

     root.left = dfs(root.left,low,high);
        root.right = dfs(root.right,low,high);

        return root;
1
2
3
4

代码实现：

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        return dfs(root,low,high);
    }
    public TreeNode dfs(TreeNode root, int low, int high){
        if(root==null){
            return null;
        }
        if(root.val<low){
            return dfs(root.right,low,high);
        }
        if(root.val>high){
            return dfs(root.left,low,high);
        }
        root.left = dfs(root.left,low,high);
        root.right = dfs(root.right,low,high);

        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

30.将有序数组转换为二叉搜索树

题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

思路：

• 确定递归终止条件

if(left>right) return null;
1

• 确定单层递归逻辑

 int mid = (right + left)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,left,mid-1);
        root.right = dfs(nums,mid+1,right);
        return root;
1
2
3
4
5

代码实现：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int[] nums, int left, int right){
        if(left > right){
            return null;
        }
        int mid = (right + left)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,left,mid-1);
        root.right = dfs(nums,mid+1,right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

31. 把二叉搜索树转换为累加树

题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

思路：

• 递归函数参数以及返回值

定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了

int pre = 0;
 public TreeNode convertBST(TreeNode root) {
 }
1
2
3

• 确定终止条件

if(root==null) return;
1

• 确定单层递归的逻辑

   //右中左
        dfs(root.right);
        root.val+=pre;
        pre = root.val;
        dfs(root.left);
        return root;
1
2
3
4
5
6

代码实现:

class Solution {
    int pre = 0; 
    public TreeNode convertBST(TreeNode root) {
        return dfs(root);
    }
    public TreeNode dfs(TreeNode root){
        if(root==null){
            return null;
        }
        //右中左
        dfs(root.right);
        root.val+=pre;
        pre = root.val;
        dfs(root.left);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17