关键词网站,四川省城乡与建设厅网站,企业seo网络推广,wordpress创建文档系统669. 修剪二叉搜索树 思路#xff1a; 这道题和删除节点异曲同工。不过要注意避坑#xff1a;当遍历到不在范围内的节点时#xff0c;不要直接返回null或直接返回其左或右孩子#xff0c;而是继续对其左或右孩子做递归。
/*** Definition for a binary tree node.* public…669. 修剪二叉搜索树 思路 这道题和删除节点异曲同工。不过要注意避坑当遍历到不在范围内的节点时不要直接返回null或直接返回其左或右孩子而是继续对其左或右孩子做递归。
/*** 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) {return dfs(root,low,high);} public TreeNode dfs(TreeNode root, int low, int high){if(rootnull) return null;if(root.vallow) return dfs(root.right,low,high);//注意不要直接返回root.rightif(root.valhigh) return dfs(root.left,low,high);root.leftdfs(root.left,low,high);root.rightdfs(root.right,low,high);return root;}
}108.将有序数组转换为二叉搜索树 思路 这道题是使用二分查找的思路递归构建二叉树。
/*** 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 getSortedArrayToBST(nums,0,nums.length-1);}public TreeNode getSortedArrayToBST(int[] nums,int left,int right){if(leftright) return null;if(leftright) return new TreeNode(nums[left]);int midleft(right-left)/2;TreeNode rootnew TreeNode(nums[mid]);root.leftgetSortedArrayToBST(nums,left,mid-1);root.rightgetSortedArrayToBST(nums,mid1,right);return root;}
}538.把二叉搜索树转换为累加树 思路 使用双指针的方法右中左的顺序遍历数组。
/*** 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 {TreeNode pre;public TreeNode convertBST(TreeNode root) {getConvertBST(root);return root;}public void getConvertBST(TreeNode node){if(nodenull) return;getConvertBST(node.right);if(pre!null){node.valnode.valpre.val;}prenode;getConvertBST(node.left);}
}
