题目地址(105. 从前序与中序遍历序列构造二叉树)

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

题目描述

  1. 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
  5. 示例 1:
  7. Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  8. Output: [3,9,20,null,null,15,7]
  11. 示例 2:
  13. Input: preorder = [-1], inorder = [-1]
  14. Output: [-1]
  19. 提示:
  21. 1 <= preorder.length <= 3000
  22. inorder.length == preorder.length
  23. -3000 <= preorder[i], inorder[i] <= 3000
  24. preorder 和 inorder 均无重复元素
  25. inorder 均出现在 preorder
  26. preorder 保证为二叉树的前序遍历序列
  27. inorder 保证为二叉树的中序遍历序列

前置知识


公司

  • 暂无

思路

image.png
image.png
知识点：

前序遍历列表：第一个元素永远是 【根节点 (root)】
中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】
算法思路：

通过【前序遍历列表】确定【根节点 (root)】
将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode buildTree(int[] preorder, int[] inorder) {
  19.             return loop(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
  20.         }
  22.        public TreeNode loop(int[] preorder, int preLeft, int preRight,
  23.                             int[] inorder, int inLeft, int inRight) {
  24.             //中止条件
  25.            if (inLeft > inRight) {
  26.                return null;
  27.            }
  28.            //找到根节点
  29.            int rootVal = preorder[preLeft];
  30.            TreeNode root = new TreeNode(rootVal);
  31.            //找到中序序列中根节点的位置
  32.            int index = 0;
  33.            for (int i = inLeft; i <= inRight ; i++) {
  34.                if (inorder[i] == rootVal) {
  35.                    index = i;
  36.                    break;
  37.                }
  38.            }
  39.            //将原序列分割成左右两个子树
  40.            int leftSize = index - inLeft;
  41.            root.left = loop(preorder , preLeft+1 , preLeft +leftSize, inorder ,inLeft ,index-1);
  42.            root.right = loop(preorder , preLeft + leftSize +1 , preRight, inorder ,index+1  ,inRight);
  43.            return root;
  44.        }
  45.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：105. 从前序与中序遍历序列构造二叉树 - 图3#card=math&code=O%28n%29&id=AeMoP)
  • 空间复杂度：105. 从前序与中序遍历序列构造二叉树 - 图4#card=math&code=O%28n%29&id=MGJwG)