1008_前序遍历构造二叉搜索树

类型：树

• 1008. 前序遍历构造二叉搜索树 💛 ⭐

  https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/

  ❓ 给定一个二叉搜索树的前序遍历结果，据此还原构建出该二叉搜索树。

  💡 前序遍历 + 中序遍历

  二叉搜索树的中序遍历结果是一个升序序列。因此对给定的前序遍历结果升序排列后可以得到中序遍历结果。之后此题与「105. 从前序与中序遍历序列构造二叉树」一致。

  class Solution:
      def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
          if not preorder:
              return None
  
          inorder = preorder[:]
          inorder.sort()
  
          def geneNode(preorder_left, preorder_right, inorder_left, inorder_right):
              if preorder_left > preorder_right:
                  return None
  
  						# 前序遍历中的第一个节点就是根节点
              preorder_root = preorder_left
  						# 在中序遍历中定位根节点
              inorder_root = index[preorder[preorder_root]]
  						# 得到左子树中的节点数目
              left_size = inorder_root - inorder_left
  						# 先把根节点建立出来
              root = TreeNode(preorder[preorder_root])
  						# 递归地构造左子树，并连接到根节点
              # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
              root.left = geneNode(preorder_left + 1, preorder_left + left_size, inorder_left, inorder_root - 1)
              # 递归地构造右子树，并连接到根节点
              # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
  						root.right = geneNode(preorder_left + left_size + 1, preorder_right, inorder_root + 1, inorder_right)
  
              return root
  
  				# 构造哈希映射，帮助我们快速定位根节点
          index = {element: i for i, element in enumerate(inorder)}
  
          length = len(preorder)
          return geneNode(0, length - 1, 0, length - 1)

  时间复杂度：O(NlogN)，空间复杂度：O(n)

  💡 二分查找分界线

  根据前序遍历的定义，前序遍历的首元素是树的根结点。

  根据搜索树的性质，可以把剩下的元素分为小于根结点和大于根结点两类，分别用于递归构建左子树和右子树。

  这两个区间的分界线，可以通过二分法来查找。

  public class Solution {
  
      public TreeNode bstFromPreorder(int[] preorder) {
          int len = preorder.length;
          if (len == 0) {
              return null;
          }
          return dfs(preorder, 0, len - 1);
      }
  
      /**
       * 根据 preorder 的子区间 [left..right] 构建二叉树
       *
       * @param preorder
       * @param left
       * @param right
       * @return
       */
      private TreeNode dfs(int[] preorder, int left, int right) {
          if (left > right) {
              return null;
          }
  
          TreeNode root = new TreeNode(preorder[left]);
          if (left == right) {
              return root;
          }
  
          // 在区间 [left..right] 里找最后一个小于 preorder[left] 的下标
          // 注意这里设置区间的左边界为 left ，不能是 left + 1
          // 这是因为考虑到区间只有 2 个元素 [left, right] 的情况，第 1 个部分为空区间，第 2 部分只有一个元素 right
          int l = left;
          int r = right;
  
          while (l < r) {
              int mid = l + (r - l + 1) / 2;
              if (preorder[mid] < preorder[left]) {
                  // 下一轮搜索区间是 [mid, r]
                  l = mid;
              } else {
                  // 下一轮搜索区间是 [l, mid - 1]
                  r = mid - 1;
              }
          }
  
          TreeNode leftTree = dfs(preorder, left + 1, l);
          TreeNode rightTree = dfs(preorder, l + 1, right);
          root.left = leftTree;
          root.right = rightTree;
          return root;
      }
  }

  时间复杂度：O(NlogN)，空间复杂度：O(n)

  💡 数值上下界递归构建

  我们在递归时维护一个 (lower, upper) 二元组，表示当前位置可以插入的节点的值的上下界。如果此时先序遍历位置的值处于上下界中，就将这个值作为新的节点插入到当前位置，并递归地处理当前位置的左右孩子的两个位置。否则回溯到当前位置的父节点。

  一开始的时候，lower 和 upper 分别为负无穷和正无穷。

  我们从前向后访问先序遍历数组，按照如下规律构建搜索树：

  • 如果当前元素的值 val 在 [lower, upper] 的范围内，则新建一个节点 root，并对其左孩子递归处理 helper(lower, val)，对其右孩子递归处理 helper(val, upper)。
  • 如果当前元素的值 val 不在 [lower, upper] 范围内，则进行回溯。

  class Solution:
  
      def __init__(self):
          self.index = 0
  
      def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
          if not preorder:
              return None
  
          upper = 2147483647
          lowwer = -2147483648
          self.index = 1
  
          def doBst(node, lowwer, upper, preorder):            
              if self.index < len(preorder) and preorder[self.index] > lowwer and preorder[self.index] < node.val:
                  node.left = TreeNode(preorder[self.index])
                  self.index += 1
                  doBst(node.left, lowwer, node.val, preorder)
  
              if self.index < len(preorder) and preorder[self.index] > node.val and preorder[self.index] < upper:
                  node.right = TreeNode(preorder[self.index])
                  self.index += 1
                  doBst(node.right, node.val, upper, preorder)
  
          head = TreeNode(preorder[0])
          doBst(head, lowwer, upper, preorder)
          return head

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 数值上下界迭代构建

  数值上下界方法也可以通过迭代来实现。

  • 将先序遍历中的第一个元素作为二叉树的根节点，即 root = new TreeNode(preorder[0])，并将其放入栈中。
  • 使用 for 循环迭代先序遍历中剩下的所有元素：
    • 将栈顶的元素作为父节点，当前先序遍历中的元素作为子节点。如果栈顶的元素值小于子节点的元素值，则将栈顶的元素弹出并作为新的父节点，直到栈空或栈顶的元素值大于子节点的元素值。注意，这里作为父节点的是最后一个被弹出栈的元素，而不是此时栈顶的元素；
    • 如果父节点的元素值小于子节点的元素值，则子节点为右孩子，否则为左孩子；
    • 将子节点放入栈中。

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class Solution {
  
      public TreeNode bstFromPreorder(int[] preorder) {
          int len = preorder.length;
          if (len == 0) {
              return null;
          }
  
          TreeNode root = new TreeNode(preorder[0]);
          Deque<TreeNode> stack = new ArrayDeque<>();
          stack.push(root);
  
          for (int i = 1; i < len; i++) {
              // 将栈的最后一个元素作为父元素，并从下一个前序遍历的节点创建子节点
              TreeNode node = stack.peekLast();
              TreeNode currentNode = new TreeNode(preorder[i]);
  
              // 栈中小于当前节点值的元素全部出栈，当前节点连接到最后一个弹出栈的结点的右边
              while (!stack.isEmpty() && stack.peekLast().val < currentNode.val) {
                  node = stack.removeLast();
              }
  
              if (node.val < currentNode.val) {
                  node.right = currentNode;
              } else {
                  node.left = currentNode;
              }
              stack.addLast(currentNode);
          }
          return root;
      }
  }

  时间复杂度：O(n)，空间复杂度：O(n)