代码随想录算法训练营第23天 二叉树 java : 669. 修剪二叉搜索树108.将有序数组转换为二叉搜索树538.把二叉搜索树转换为累加树

LeetCode 669. 修剪二叉搜索树

题目讲解

思路

在1到3的区间选择 元素 如何超过3 或者 小于1

• 如果小于1 叫要考虑 它的右子树
• 如果 大于3的 就要考虑它的左子树

/**
 * 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 trimBST(TreeNode root, int low, int high) {
        if( root ==null)
        return null;
        if( root.val <low)
        return trimBST(root.right,low,high);
        if(root.val>high)
        return trimBST(root.left,low,high);
        root.left= trimBST(root.left,low,high);
        root.right = trimBST(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
21
22
23
24
25
26
27
28

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

题目讲解

思路

如果 为奇数 right-left ==1 return new TreeNode( nums[left] );
如果为 偶数 int mid =left+(right-left)/2

递归终止条件 这里定义的是左闭右闭得区间，所以当区间 left> right 就是空节点了。

  TreeNode root =new TreeNode(nums[mid]);
1

---

/**
 * 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 sortedArrayToBST(int[] nums) {
        return transler( nums,0,nums.length);

    }
    public TreeNode transler(int[ ] nums, int left,int right)
    {
        if( left>=right)
        return null;
        if( right- left ==1)
        return new TreeNode( nums[left]);
        int middle =( left+(right-left)/2);
        TreeNode root = new TreeNode( nums[middle]);
        root.left = transler(nums,left,middle);
        root.right = transler(nums,middle+1,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
30
31
32
33

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

题解

思路

左中右 从小到大遍历 这是中序遍历 右中左 从大到小
倒序遍历

单层递归逻辑

traversal(cur->right);  // 右
cur->val += pre;        // 中
pre = cur->val;
traversal(cur->left);   // 左
1
2
3
4

/**
 * 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 {
    int sum;
    public TreeNode convertBST(TreeNode root) {
          sum =0;
          convertBST1( root);
          return root;
    }
    public void convertBST1( TreeNode root)
    {
        if( root ==null)
        {
            return;
        }
        convertBST1(root.right);
        sum+= root.val;
        root.val =sum;
        convertBST1(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
26
27
28
29
30
31
32
33
34

总结

永远饥饿 永远疲惫 永远孤独