669. 修剪二叉搜索樹?

題目

參考文章

思路：這題其實(shí)就是刪除不符合上下邊界的節(jié)點(diǎn)。注意：這里刪除不符合上下邊界節(jié)點(diǎn)時(shí)，這個(gè)不符合上下邊界的節(jié)點(diǎn)的左或右子樹可能存在符合上下邊界的節(jié)點(diǎn)，所i有每次比較完之后，要繼續(xù)遍歷其左或右子樹，直到把所有不符合上下邊界的節(jié)點(diǎn)都刪除為止

代碼：

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); //當(dāng)當(dāng)前節(jié)點(diǎn)值小于下邊界時(shí)，就直接繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)的右子樹即可，找到符合上下邊界的值}if (root.val > high) {//當(dāng)當(dāng)前節(jié)點(diǎn)值大于上邊界時(shí)，就直接繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)的左子樹即可，找到符合上下邊界的值return trimBST(root.left, low, high);}// root在[low,high]范圍內(nèi)//接入如何條件的左右孩子root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}

108.將有序數(shù)組轉(zhuǎn)換為二叉搜索樹?

題目

參考文章

思路：這道題目是構(gòu)造平衡二叉搜索樹，所以我們構(gòu)造的時(shí)候，不能只在節(jié)點(diǎn)的某一邊構(gòu)造。因此我們要從數(shù)組的中間位置開始構(gòu)造根節(jié)點(diǎn)，我們采用左閉右開的方式。因?yàn)槭亲箝]右開，所以非法條件為 left>=right；然后每次取中間數(shù)組位置構(gòu)建值，構(gòu)建完后又繼續(xù)構(gòu)建左右節(jié)點(diǎn)

代碼：

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}public TreeNode sortedArrayToBST(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {//當(dāng)遍歷到當(dāng)前數(shù)組的的下標(biāo)位置相差1時(shí)，表示已經(jīng)在數(shù)組邊界，所以直接構(gòu)建節(jié)點(diǎn)返回即可return new TreeNode(nums[left]);}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(nums, left, mid);root.right = sortedArrayToBST(nums, mid + 1, right);return root;}
}

538.把二叉搜索樹轉(zhuǎn)換為累加樹?

題目

參考文章

思路：這題目的意思就是讓我們從這個(gè)二叉搜索樹從大到小遍歷，原來(lái)左中右的情況是從小到大遍歷，所以從大到小遍歷就是右中左。了解這個(gè)這題目就很好解決了。這里設(shè)置一個(gè)int sum，用于存儲(chǔ)累加值，而且每次累加后，當(dāng)前記得的值就更新為sum（題目要求），按右中左去遍歷即可

代碼：

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

二叉樹總結(jié)

在二叉樹題目選擇什么遍歷順序是不少同學(xué)頭疼的事情，我們做了這么多二叉樹的題目了，Carl給大家大體分分類。

• 涉及到二叉樹的構(gòu)造，無(wú)論普通二叉樹還是二叉搜索樹一定前序，都是先構(gòu)造中節(jié)點(diǎn)。

• 求普通二叉樹的屬性，一般是后序，一般要通過遞歸函數(shù)的返回值做計(jì)算。

• 求二叉搜索樹的屬性，一定是中序了，要不白瞎了有序性了。

注意在普通二叉樹的屬性中，我用的是一般為后序，例如單純求深度就用前序，二叉樹：找所有路徑?(opens new window)也用了前序，這是為了方便讓父節(jié)點(diǎn)指向子節(jié)點(diǎn)。

所以求普通二叉樹的屬性還是要具體問題具體分析。