Come n times - 07. Rebuild the binary tree

专栏前言:

本专栏主要是算法训练,目的很简单.在掌握基本的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：

I have written my thoughts on this question below,more practice

/** * 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<>();
        //Push the root node onto the stack
        stack.push(root);
        //Define an inorder traversal subscript
        int inorderIndex = 0;
        //循环前序遍历
        for(int i = 1; i < preorder.length; ++i){
    
            //The value of the preorder traversal
            int preorderVal = preorder[i];
            //Find the top value of the stack
            TreeNode node = stack.peek();
            //If the value at the top of the stack is not equal The first value of the inorder traversal
            if(node.val != inorder[inorderIndex]){
    
                //Then the value is the left child of the root node,Push the left child onto the stack
                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. 从前序与中序遍历序列构造二叉树	中等