938. 二叉搜索樹的范圍和

給定二叉搜索樹的根結點 root，返回值位于范圍 [low, high] 之間的所有結點的值的和。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-of-bst
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路及方法

遞歸，但我的方法沒有用BST的性質，還可以修改。

/**
 * 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;
    }
}

結果如下：

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

給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉換為一棵 高度平衡 二叉搜索樹。

高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路及方法

類似于二分查找的方法，因為有序。先讓數(shù)組最中間的值成為根節(jié)點，然后縮小范圍即可。

/**
 * 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;
    }
}

結果如下：

110. 平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/balanced-binary-tree
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路及方法

雙重遞歸的思想，一個用來獲得二叉樹子樹的高度，另一個用來判斷每個節(jié)點子樹的高度差。
注意：每個節(jié)點都要判斷。

/**
 * 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));
    }
}

結果如下：