LeetCode：669. 修剪二叉搜索樹

問題描述

解決方案：

1.思路

2.代碼實現

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);} else if (root.val > high) {return trimBST(root.left, low, high);} else {root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}

3.復雜度分析

LeetCode：108.將有序數組轉換為二叉搜索樹

問題描述

解決方案：

1.思路：

• 考慮到是構建高度平衡的搜索二叉樹，所以可以總是選擇中間位置左邊的數字作為根節點；

2.代碼實現

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 總是選擇中間位置左邊的數字作為根節點int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

3.復雜度分析

LeetCode：538.把二叉搜索樹轉換為累加樹

問題描述

解決方案：

1.思路：

2.代碼實現

public TreeNode convertBST(TreeNode root) {if (root != null) {convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);}return root;
}

3.復雜度分析