0%

# Leetcode 105 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal) 题解分析

Posted on 2020-12-13 In Java , leetcode , Binary Tree , java , Binary Tree , DFS Views: Views: Disqus:

## 题目介绍

Given preorder and inorder traversal of a tree, construct the binary tree.
给定一棵树的前序和中序遍历，构造出一棵二叉树

### 注意

You may assume that duplicates do not exist in the tree.
你可以假设树中没有重复的元素。(PS: 不然就没法做了呀)

### 例子:

    1
    2
    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

返回的二叉树

    1
    2
    3
    4
    5
      3
     / \
    9  20
      /  \
     15   7

## 简要分析

看到这个题可以想到一个比较常规的解法就是递归拆树，前序就是根左右，中序就是左根右，然后就是通过前序已经确定的根在中序中找到，然后去划分左右子树，这个例子里是 3，找到中序中的位置，那么就可以确定，9 是左子树，15,20,7是右子树，然后对应的可以根据左右子树的元素数量在前序中划分左右子树，再继续递归就行

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
          // 获取下数组长度
            int n = preorder.length;
            // 排除一下异常和边界
            if (n != inorder.length) {
                return null;
            }
            if (n == 0) {
                return null;
            }
            if (n == 1) {
                return new TreeNode(preorder[0]);
            }
            // 获得根节点
            TreeNode node = new TreeNode(preorder[0]);
            int pos = 0;
            // 找到中序中的位置
            for (int i = 0; i < inorder.length; i++) {
                if (node.val == inorder[i]) {
                    pos = i;
                    break;
                }
            }
            // 划分左右再进行递归，注意下`Arrays.copyOfRange`的用法
            node.left = buildTree(Arrays.copyOfRange(preorder, 1, pos + 1), Arrays.copyOfRange(inorder, 0, pos));
            node.right = buildTree(Arrays.copyOfRange(preorder, pos + 1, n), Arrays.copyOfRange(inorder, pos + 1, n));
            return node;
        }
    }

Related Posts

- Leetcode 104 二叉树的最大深度(Maximum Depth of Binary Tree) 题解分析
- Leetcode 2 Add Two Numbers 题解分析
- Leetcode 3 Longest Substring Without Repeating Characters 题解分析
- Leetcode 234 回文链表(Palindrome Linked List) 题解分析
- Leetcode 155 最小栈(Min Stack) 题解分析

请我喝杯咖啡

WeChat Pay

Alipay

- Post author: Nicksxs
- Post link: https://nicksxs.me/2020/12/13/Leetcode-105-从前序与中序遍历序列构造二叉树-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal-题解分析/
- Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.