( Leetcode 刷题)将有序数组转换为二叉搜索树、二叉搜索树中的搜索

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
108. 将有序数组转换为二叉搜索树

解法1 递归

这题需要构造树，有两个条件

构造一棵二叉搜索树
构造的树高度要平衡

再来看题目条件，给的是一组升序排列的有序数组，要想构造一棵二叉搜索树，从数组中取一个值root.val，生成树的root结点，在数组中root.val前面的数组成的数组属于要构造树的左子树，同理后面的数属于右子树，很显然可以递归出一棵二叉搜索树。
现在只满足了题目的一个条件，我们还需要让构造的树高度平衡。一种最简单的办法是取根节点时取数组中间的那个数生成根节点。因为这样能保证每个节点的左右子树节点数相同或差1，树总是平衡的。
组合起来代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = sortedArrayToBST(0, nums.length - 1, nums);
        return root;
    }

    public TreeNode sortedArrayToBST(int start, int end, int[] nums) {
        if (start > end) {
            return null;
        }
        int p = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = sortedArrayToBST(start, p - 1, nums);
        root.right = sortedArrayToBST(p + 1, end, nums);
        return root;
    }
}

题目描述

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。
700. 二叉搜索树中的搜索

解法1 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        } else if (root.val < val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        }
    }
}

解法2 迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        //层序遍历节点
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                root = queue.poll();
                if (root.val == val) {
                    return root;
                }
                //根据二叉搜索树的性质，val 比当前节点值大，往右子树搜索即可
                if (root.val < val && root.right != null) {
                    queue.add(root.right);
                }
                //同理
                if (root.val > val && root.left != null) {
                    queue.add(root.left);
                }
            }
        }
        return null;
    }
}

最后编辑于：2020.07.06 17:38:34