前言

今天是第一轮学习LeetCode二叉树的最后一天啦，今天还是继续学习一下二叉搜索树的内容，希望博主记录的内容能够对大家有所帮助 ，一起加油吧朋友们！💪💪💪

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

LeetCode题目链接

给一个升序的整数数组，把它转换成一棵平衡二叉搜索树

1728608107541

我们来思路梳理

我们进一步来梳理递归三要素

1
2
3
//返回值需要返回构建好的平衡二叉搜索树的根节点
//参数值的话需要分割数组的左右下标与数组
private TreeNode traversal(int[] nums, int left, int right){}
1
2
//因为是递归处理每个数组的值，无法分割时结束递归
if(left > right)return null;//递归出口
1
2
3
4
5
6
/**单层处理逻辑 */
int mid = left + (right - left) / 2;//取中间值
TreeNode node = new TreeNode(nums[mid]);//构建节点
node.left = traversal(nums, left, mid - 1);//递归构建左孩子
node.right = traversal(nums, mid + 1, right);//递归构建右孩子
return node;

递归法的完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 /**递归法 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }
    private TreeNode traversal(int[] nums, int left, int right){
        if(left > right)return null;//递归出口

        /**单层处理逻辑 */
        int mid = left + (right - left) / 2;//取中间值
        TreeNode node = new TreeNode(nums[mid]);//构建节点
        node.left = traversal(nums, left, mid - 1);//递归构建左孩子
        node.right = traversal(nums, mid + 1, right);//递归构建右孩子
        return node;
    }
}

我们进一步来梳理迭代法

迭代法的完整代码如下

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
30
31
32
33
34
35
36
37
38
39
/**迭代法 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0)return null;//提前结束

        TreeNode root = new TreeNode(0);//初始化根节点
        Queue<TreeNode> nodeQue = new LinkedList<>();//存储遍历节点
        Queue<Integer> leftQue = new LinkedList<>();//存储左区间下标
        Queue<Integer> rightQue = new LinkedList<>();//存储右区间下标
        nodeQue.offer(root);
        leftQue.offer(0);
        rightQue.offer(nums.length - 1);
        while(!nodeQue.isEmpty()){
            TreeNode cur = nodeQue.poll();
            int left = leftQue.poll();
            int right = rightQue.poll();
            int mid = left + (right - left) / 2;
            cur.val = nums[mid];

            if(left <= mid - 1){//处理左孩子
                cur.left = new TreeNode(0);
                nodeQue.offer(cur.left);
                leftQue.offer(left);
                rightQue.offer(mid - 1);
            }

            if(right >= mid + 1){//处理右孩子
                cur.right = new TreeNode(0);
                nodeQue.offer(cur.right);
                leftQue.offer(mid + 1);
                rightQue.offer(right);
            }
        }
        return root;


    }
    
}

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

LeetCode题目链接

1728609679671

我们来思路梳理

我们来梳理递归三要素

1
2
3
//在已有二叉搜索树根节点root存在的情况下去修改其每个节点的值，这里递归的时候不需要返回节点什么的所以返回值为void
//参数的话就是要处理的二叉搜索树的根节点
private void traversal(TreeNode root){}
1
2
//因为是递归处理每个节点，所以处理到空节点递归结束
if(root == null)return;
1
2
3
4
traversal(root.right);//先处理右节点
root.val += pre;//累加值
pre = root.val;//更新前序节点值
traversal(root.left);//再处理左节点

递归完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**递归法 */
class Solution {
    private int pre = 0;
    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }

    private void traversal(TreeNode root){//右中左遍历
        if(root == null)return;
        traversal(root.right);
        root.val += pre;
        pre = root.val;
        traversal(root.left);
    }
}

我们来进一步梳理迭代法的思路

迭代的完整代码如下

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
/**迭代法 */
class Solution {
    private int pre = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null)return root;
        traversal(root);
        return root;
    }

    private void traversal(TreeNode root){//右中左遍历
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.right; //压栈中右
            }else{
                cur = stack.pop();//中
                cur.val += pre;
                pre = cur.val;
                cur = cur.left; //左
            }
        }
    }
}

总结

明天博主将开始回溯算法的第一轮学习，大家一起加油呀✊✊✊