重點：一般二叉樹多考慮遍歷順序，

二叉搜索樹多考慮特性，不用考慮遍歷順序。

一、[108]將有序數組轉換為二叉搜索樹

左閉右開

偶數取左邊

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums,0, nums.length);}//[left,right)public TreeNode traversal(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {return new TreeNode(nums[left]);}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums, left, mid);root.right = traversal(nums, mid + 1, right);return root;}
}

二、[538]把二叉搜索樹轉換為累加樹

雙指針

class Solution {int pre=0;public TreeNode convertBST(TreeNode root) {traversal(root);return root;}// 按右中左順序遍歷，累加即可void traversal(TreeNode cur) {if (cur == null) {return;}traversal(cur.right);cur.val = pre+ cur.val;pre= cur.val;traversal(cur.left);}
}

三、[669]修剪二叉搜索樹

一般先考慮抽出一個子樹，即左根右三個節點，之后根據條件，看往左子樹還是右子樹

方向前進，或者結束遞歸返回。

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在[low,high]范圍內root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}

?