展示網(wǎng)站動(dòng)畫(huà)怎么做的站長(zhǎng)工具seo綜合查詢(xún)官網(wǎng)
669.修剪二叉搜索樹(shù)
這道題目需要考慮當(dāng)前節(jié)點(diǎn)是否在[low,high]之間，
因?yàn)槭瞧胶舛鏄?shù)，
所以當(dāng)當(dāng)前節(jié)點(diǎn)值小于low時(shí)，那么其左節(jié)點(diǎn)肯定更小，因此刪除該節(jié)點(diǎn)的方式是給root節(jié)點(diǎn)返回其右節(jié)點(diǎn)的遞歸，注意：這里不是直接返回右節(jié)點(diǎn)，是因?yàn)樵谟易訕?shù)中也有可能存在不滿(mǎn)足條件的節(jié)點(diǎn)，需要繼續(xù)遞歸排查；
當(dāng)當(dāng)前節(jié)點(diǎn)值大于high時(shí)，那么其右節(jié)點(diǎn)肯定更大，因此刪除該節(jié)點(diǎn)的方式是給root節(jié)點(diǎn)返回其左節(jié)點(diǎn)的遞歸。
如果root.val符合在[low,high]的區(qū)間內(nèi)，其左右節(jié)點(diǎn)承接左右節(jié)點(diǎn)的返回值即可。
最終返回root。
代碼如下：
/*** 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;else if(root.val < low) return trimBST(root.right,low,high);else 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;}
}
108.將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
每次取中間索引的值構(gòu)造節(jié)點(diǎn)，利用遞歸構(gòu)造平衡二叉搜索樹(shù)。
要注意限定左右指針的大小條件：if(right < left) return 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 sortedArrayToBST(int[] nums) { if(nums.length == 0) return null;return build(nums,0,nums.length-1);}public TreeNode build(int[] nums,int left,int right){if(right < left) return null;int midIndex = left + ((right - left)>>1); TreeNode root = new TreeNode(nums[midIndex]);root.left = build(nums,left,midIndex-1);root.right = build(nums,midIndex+1,right);return root;}
}
538.把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)
如果是一個(gè)數(shù)組[-10,-4,4,6,7,9]要計(jì)算每個(gè)位置的累加–>[12,22,26,22,16,9]，可以定義一個(gè)pre，記錄每一次前一個(gè)數(shù)的累加，然后到自身節(jié)點(diǎn)之后再加上自己本身的值。
那么這道題也可以在類(lèi)中定義一個(gè)全局變量pre來(lái)記錄每次累加的結(jié)果，然后通過(guò)右中左的順序去便利，已以到使每個(gè)節(jié)點(diǎn) node 的新值等于原樹(shù)中大于或等于 node.val 的值之和的目的：
/*** 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 pre = 0;public TreeNode convertBST(TreeNode root) {plusProcess(root);return root;}public void plusProcess(TreeNode root){//右中左遍歷//終止條件if(root == null) return;//右plusProcess(root.right);//中pre += root.val;root.val = pre;//每次改變r(jià)oot節(jié)點(diǎn)的值//左plusProcess(root.left);}
}