代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树,108.将有序数组转换为二叉搜索树,538.把二叉搜索树转换为累加树_isaac_mz的博客-爱代码爱编程
669. Trim a Binary Search Tree
- 思路
- 递归
-
java class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null){ return root; } //节点小于low时,根据BST特性,其右子树可能存在范围内的节点 //返回trimBST(root.right, low, high) if (root.val < low){ return trimBST(root.right, low, high); } //节点大于high时,根据BST特性,其左子树可能存在范围内的节点 //返回trimBST(root.left, 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; } }
-
- 迭代
-
java class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null){ return root; } // 处理头节点,保证头节点在范围内 while (root != null && (root.val < low || root.val > high)){ if (root.val < low){ root = root.right; }else{ root = root. left; } } //处理左子树 TreeNode cur = root; while (cur != null){ while(cur.left != null && cur.left.val < low){ cur.left = cur.left.right; } cur = cur.left; } //重新回到右子树,这步有点像回溯 cur = root; //处理右子树 while (cur != null){ while(cur.right != null && cur.right.val >high){ cur.right = cur.right.left; } cur = cur.right; } return root; } }
- 递归
108. Convert Sorted Array to Binary Search Tree
- 思路
- 递归
-
java class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length-1); } private 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; } }
538. Convert BST to Greater Tree
- 思路
- 递归遍历
- 倒序遍历(右中左)累加
-
java class Solution { int pre; public TreeNode convertBST(TreeNode root) { pre = 0; helper(root); return root; } private void helper (TreeNode root){ if (root == null){ return; } helper( root.right); pre += root.val; root.val = pre; helper(root.left); } }
- 迭代法
- 右中左
-
java class Solution { int pre; public TreeNode convertBST(TreeNode root) { pre = 0 ; helper(root); return root; } private void helper (TreeNode root){ Stack stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if(cur != null){ stack.push(cur); cur = cur.right; //右 }else{ // 中 cur = stack.pop(); pre = pre + cur.val; cur.val = pre; // 左 cur=cur.left; } } } }