[LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal (java)

题目

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)


Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

在这里插入图片描述
Note:

1 <= preorder.length <= 100
The values of preorder are distinct.


翻译

  • 先序遍历构造二叉树

返回与给定先序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。

(回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left 的任何后代,值总 < node.val,而 node.right 的任何后代,值总 > node.val。此外,先序遍历首先显示节点的值,然后遍历 node.left,接着遍历 node.right。)

思路

  • 给定的输入数组是二叉搜索树按照先序遍历得到的
    • 二叉搜索树:根的值比所有左子树节点值都大,比所有右子树节点值都小
    • 先序遍历:先访问根,然后左节点,最后右节点
  • 根据二叉搜索树和先序遍历的特点,由下图可知,关键是找到第一个大于根节点值的下标,左侧为根节点左子树(5,1,7),右侧(包括其)为根节点右子树(10,12)
  • 因为其为先序遍历,所有左子树的根为左侧第一个节点(5),右子树的根为右侧第一个节点(10)
  • 依次进行,得到最终的树
    在这里插入图片描述

代码

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 0) return null;
        return bstFromPreorder(preorder, 0, preorder.length - 1);
    }

    public TreeNode bstFromPreorder(int[] preorder, int left, int right) {
        if (left > right) return null;
        TreeNode node = new TreeNode(preorder[left]);
        int i = left + 1;
        for (; i <= right; i++) {
            if (preorder[i] > preorder[left]) break;
        }
        node.left = bstFromPreorder(preorder, left + 1, i - 1);
        node.right = bstFromPreorder(preorder, i, right);
        return node;
    }
}
原文链接:加载失败,请重新获取