题解 | #重建二叉树#

基本都是递归方法的题解，这里提供一个迭代方法的题解，方法很巧妙，具体思路来自leetcode-105
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int len = pre.length;
        if(len==0) return null;
        TreeNode root = new TreeNode(pre[0]);
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        int inIndex = 0;
        for(int i=1;i<len;i++){
            int val = pre[i];
            TreeNode node = s.peek();
            if(node.val!=in[inIndex]){
                node.left = new TreeNode(val);
                s.push(node.left);
            }
            else{
                while(!s.isEmpty() && s.peek().val==in[inIndex]){
                    node = s.pop();
                    inIndex++;
                }
                node.right = new TreeNode(val);
                s.push(node.right);
            }
        }
        return root;
    }
}