@@ -90,4 +90,53 @@ public TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inor
9090 root .right = buildTreeHelper (preorder , pStart + leftNum + 1 , pEnd , inorder , iRootIndex + 1 , iEnd );
9191 return root ;
9292 }
93+ }
94+
95+
96+ /*
97+ 迭代：
98+ 1、用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点
99+ 2、依次枚举前序遍历中除了第一个节点以外的每个节点
100+ 1）如果 index 恰好指向栈顶节点，那么不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子
101+ 2）如果 index 和栈顶节点不同，将当前节点作为栈顶节点的左儿子
102+ 3）无论是哪一种情况，最后都将当前的节点入栈
103+
104+ preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
105+ inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
106+ 3
107+ / \
108+ 9 20
109+ / / \
110+ 8 15 7
111+ / \
112+ 5 10
113+ /
114+ 4
115+ */
116+ class Solution {
117+ public TreeNode buildTree (int [] preorder , int [] inorder ) {
118+ if (preorder == null || preorder .length == 0 ) {
119+ return null ;
120+ }
121+ TreeNode root = new TreeNode (preorder [0 ]);
122+ Deque <TreeNode > stack = new ArrayDeque <>();
123+ stack .push (root );
124+ int inorderIndex = 0 ;
125+ for (int i = 1 ; i < preorder .length ; i ++) {
126+ int preorderVal = preorder [i ];
127+ TreeNode node = stack .peek ();
128+ if (node .val != inorder [inorderIndex ]) {
129+ node .left = new TreeNode (preorderVal );
130+ stack .push (node .left );
131+ } else {
132+ while (!stack .isEmpty () && stack .peek ().val == inorder [inorderIndex ]) {
133+ node = stack .pop ();
134+ inorderIndex ++;
135+ }
136+ node .right = new TreeNode (preorderVal );
137+ stack .push (node .right );
138+ }
139+ }
140+ return root ;
141+ }
93142}
0 commit comments