来n遍剑指--07. 重建二叉树

专栏前言:

本专栏主要是算法训练，目的很简单。在掌握基本的java知识后，学习最重要的算法知识，在学习之前首先要对自身有一定的理解，如果不知道怎么做欢迎来私聊。

算法的过程很枯燥，但是也很特别，不断地刷题，不断地分享才会越来越好，给别人讲明白才是真正学会了。在分享中学会知识。
坚持就是胜利~~~

题目链接

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例1：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例2：

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

解题1：

这个问题我将思路写在了下方，多练熟记

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        if(preorder == null || preorder.length == 0){
    
            return null;
        }
        //根节点
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        //将根节点推入栈中
        stack.push(root);
        //定义一个中序遍历下标
        int inorderIndex = 0;
        //循环前序遍历
        for(int i = 1; i < preorder.length; ++i){
    
            //前序遍历的值
            int preorderVal = preorder[i];
            //找到栈顶值
            TreeNode node = stack.peek();
            //如果栈顶的值不等于 中序遍历的第一个值
            if(node.val != inorder[inorderIndex]){
    
                //那么该值就是根节点的左孩子，将左孩子推入栈中
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            }else{
    
                while(!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]){
    
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

课后习题：

序号	题目链接	难度评级
1	105. 从前序与中序遍历序列构造二叉树	中等