938. 二叉搜索樹的范圍和
給定二叉搜索樹的根結(jié)點(diǎn) root地沮，返回值位于范圍 [low, high] 之間的所有結(jié)點(diǎn)的值的和嗜浮。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-of-bst
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)摩疑，非商業(yè)轉(zhuǎn)載請注明出處危融。
解題思路及方法
遞歸，但我的方法沒有用BST的性質(zhì)雷袋，還可以修改吉殃。
/**
* 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 getBST(nums, 0, nums.length - 1);
}
public TreeNode getBST(int[] nums, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = getBST(nums, left, mid - 1);
root.right = getBST(nums, mid + 1, right);
return root;
}
}
結(jié)果如下：
108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
給你一個(gè)整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列楷怒，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹蛋勺。
高度平衡 二叉樹是一棵滿足「每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對值不超過 1 」的二叉樹。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有鸠删。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)抱完，非商業(yè)轉(zhuǎn)載請注明出處。
解題思路及方法
類似于二分查找的方法冶共，因?yàn)橛行蚯颉Ｏ茸寯?shù)組最中間的值成為根節(jié)點(diǎn)，然后縮小范圍即可捅僵。
/**
* 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 getBST(nums, 0, nums.length - 1);
}
public TreeNode getBST(int[] nums, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = getBST(nums, left, mid - 1);
root.right = getBST(nums, mid + 1, right);
return root;
}
}
結(jié)果如下：
110. 平衡二叉樹
給定一個(gè)二叉樹家卖，判斷它是否是高度平衡的二叉樹。
本題中庙楚，一棵高度平衡二叉樹定義為：一個(gè)二叉樹每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對值不超過 1 上荡。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/balanced-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處酪捡。
解題思路及方法
雙重遞歸的思想叁征，一個(gè)用來獲得二叉樹子樹的高度，另一個(gè)用來判斷每個(gè)節(jié)點(diǎn)子樹的高度差逛薇。
注意：每個(gè)節(jié)點(diǎn)都要判斷捺疼。
/**
* 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 boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}
結(jié)果如下：
