从前序中序遍历序列构造二叉树的迭代算法理解_前序中序构造二叉树 迭代法

力扣上这道题的大神的迭代解法不是特别好理解，比如 详细通俗的思路分析，多解法 的迭代算法，看着解法新颖，但是我看了大半天都吃不透。后来想到了一个关于栈的算法题，就是给定两个数组 A 和 B，A 代表的是元素入栈的顺序，问 B 的元素顺序是不是 A 的出栈顺序。可以说，理解了出栈顺序这道题，基本就理解了这个二叉树构造的迭代算法了。

数组 A ：[1,2,3,4,5]，数组 B1 ：[5,4,3,2,1]，B2：[4,5,3,2,1]，B3 ：[3,4,5,2,1]。数组 B1,B2,B3 均是数组 A 的合法出栈顺序。我们可以发现，每次都是从 A 里面拿元素放入栈中，然后看栈顶元素值是不是和数组 B 指针指向的值相等，相等则弹出，否则不断将数组 A 的元素入栈。

而构造树，相对出栈顺序而言，要复杂一点，首先它是二维的，再一个就是任一节点都和根节点一样，也代表了一棵树，具有递归属性。

public static TreeNode build(int[] preArr, int[] inArr){
	if (preArr == null || inArr == null || preArr.length != inArr.length || inArr.length == 0)
		return null;
	int pre = 0, in = 0;
	TreeNode root = new TreeNode(preArr[pre++]), curRoot = root;
	Stack<TreeNode> s = new Stack<>();
	s.push(root);
	while (pre < preArr.length){
		if (s.peek().val == inArr[in]){
			while (!s.isEmpty() && s.peek().val == inArr[in]){
				curRoot = s.pop();
				in++;
			}
			curRoot.right = new TreeNode(preArr[pre++]);
			s.push(curRoot.right);
			curRoot = curRoot.right;
		} else {
			curRoot.left = new TreeNode(preArr[pre++]);
			s.push(curRoot.left);
			curRoot = curRoot.left;
		}
	}		
	return root;
}

我的理解如下：

1. while 不断遍历前序数组 （出栈题是遍历数组 A）
2. 每次都是先检查栈顶元素是不是等于中序指针指向的元素，然后根据情况入栈 （出栈题也是入栈前，检查栈顶元素是否
等于数组 B 指针指向的值）
	a. 不相等，说明前序数组指针指向的元素是栈顶元素的左子节点
	b. 相等，说明栈顶节点的左子树遍历完了或者为空
	c. 第二个 while 循环是针对某个节点子孙节点都没有右子树的情况
3. 出栈完了后，那么此时的前序元素是 curRoot 节点的右子节点 （出栈题是一维的，树是二维的，所以要用 curRoot 
维持状态，至于为什么是右子节点看文中链接作者给出的反证法）
4. curRoot 的右子节点也需要入栈，然后 curRoot 指向这个右子节点继续遍历
5. 此时，等于完成了一轮根节点的所有左子树节点入栈的过程，入栈和出栈过程中关联节点。当 curRoot 指向某个节点
的右子树节点时，此时的 curRoot 就和 root 性质一样了，逻辑上是“递归”以它为“根”节点的子树遍历过程