LeetCode 精选 TOP 面试题(Java 实现)—— 从前序与中序遍历序列构造二叉树

文章目录

一、题目描述

1.1 题目
  • 从前序与中序遍历序列构造二叉树

  • 根据一棵树的前序遍历与中序遍历构造二叉树。

  • 注意:
    你可以假设树中没有重复的元素。

  • 例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
  • 返回如下的二叉树:
    3
   / \
  9  20
    /  \
   15   7
1.2 知识点
  • 二叉树
1.3 题目链接

二、解题思路

2.1 自研思路

  解题的思路即首先前序数组中首个元素即为当前二叉树的跟,所以先将根结点创建,然后在中序数组中查找此根节点,在中序数组中查找到根节点的位置后,根节点在中序数组中左侧的元素即为其左结点,其右侧的元素即为其右结点,明确了这点之后再通过递归,分别构建其左右子树即可。

  简单介绍一下代码实现中的变量含义:

  • preStart :当前轮在前序遍历序列中开始的位置;
  • preEnd :当前轮在前序遍历序列中结束的位置;
  • inStart :当前轮在中序遍历序列中开始的位置;
  • inEnd :当前轮在中序遍历序列中结束的位置;
  • leftLength :当前轮左子树的节点数量;
  • leftPreEnd :当前轮前序遍历序列中左子树结束的位置;
  • rootIndex :当前轮根节点在前序遍历序列中的位置;

三、实现代码

3.1 自研实现(Java)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private HashMap<Integer, Integer> map = new HashMap<>();
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = inorder.length;
        if(len == 0) return null;

        this.preorder = preorder; 
        this.inorder = inorder;
        for(int i = 0; i < len; i++)
            map.put(inorder[i], i);

        return buildTree(0, len-1, 0, len-1);
    }

    private TreeNode buildTree(int preStart, int preEnd, int inStart, int inEnd) {

        TreeNode root = new TreeNode(preorder[preStart]);
        if(preStart == preEnd && inStart == inEnd && preorder[preStart] == inorder[inStart])
            return root;

        int rootIndex = map.get(root.val);
        int leftLength = rootIndex - inStart;
        int leftPreEnd = preStart + leftLength;
        if(leftLength > 0)
            root.left = buildTree(preStart+1, leftPreEnd, inStart, rootIndex-1);
        if(leftPreEnd < preEnd)
            root.right = buildTree(leftPreEnd+1, preEnd, rootIndex+1, inEnd);

        return root;
    }
}
3.2 C++ 实现
LeetCode 精选 TOP 面试题(Java 实现)—— 从前序与中序遍历序列构造二叉树LeetCode 精选 TOP 面试题(Java 实现)—— 从前序与中序遍历序列构造二叉树 杨小帆_ 发布了260 篇原创文章 · 获赞 32 · 访问量 3万+ 私信 关注
上一篇:将VB的Val转换为Java?


下一篇:将Yolov5的detect.py修改为可以直接调用的函数