二叉树的前中后序迭代写法
既然是迭代，肯定需要用到栈，那么如何思考3种遍历方法是怎么运用栈的呢？
前序遍历，就是先根节点，再左孩子，然后右孩子。
一开始我们把根节点放进栈里。然后就弹出来VISIT，这样确保了先访问了根节点。根据栈后进先出的特性，这时我们需要先把右孩子放进栈里，然后是左孩子。
下面是代码
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if(root==null) return res;
st.push(root);
while(!st.isEmpty()){
TreeNode cur = st.pop();
res.add(cur.val);
if(cur.right!=null) st.push(cur.right);
if(cur.left!=null) st.push(cur.left);
}
return res;
}
前序遍历的思考轨迹还是比较容易。下面是中序遍历。中序遍历要求先左孩子然后是根节点。所以当根节点放进去的时候，不应该立刻出来。因为左孩子优先。那么就一路向左，一条路走到黑，左到不能左。这里有一个门槛，就是如果到左了，下面就把最左的弹出来。这个时候如果是WHILE循环，那么栈顶的左又会因为一路向左的代码，又把左孩子塞回去。那么就是个死循环。错误代码如下
while(!st.isEmpty()){
while(st.peek().left!=null)
st.push(st.peek().left);
TreeNode cur = st.pop();
res.add(cur.val);
if(cur.right!=null) st.push(cur.right);
}
为了避免上述情况，我们需要额外一个NODE节点，当做CUR。然后通过CUR节点，来防止使用栈顶节点来走一路向左的逻辑。下面就会产生正确代码。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root;
while(!st.isEmpty() || cur!=null){
while(cur != null){
st.push(cur);
cur = cur.left;
}
cur = st.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
最后我们来思考后序遍历，就是先左孩子，后右孩子，最后是根节点。那么我们还是借用中序遍历的思想，一路做到底，利用一个CUR节点。但是左到低之后，还要看有没有右孩子，如果有右孩子，还需先把右孩子处理下。如果没有，就可以访问当前节点了。不难得出如下错误代码
while(!st.isEmpty() || cur!=null){
while(cur != null){
st.push(cur);
cur = cur.left;
}
if(st.peek().right !=null){
cur = st.peek().right;
}else{
res.add(st.pop().val);
}
}
这里就是把右节点放到栈里。随后出栈。随后ST.PEEK右节点又不为空了。那么这个右节点就反复进出。为了避免这种情况，我们需要引入一个lastvisit 的节点。来切断这个情况。如果右节点不为空，并且LASTVISIT 不是这个右节点。那么才去指向右节点。不然就接着POP。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode lastVisit = null;
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root;
while(!st.isEmpty() || cur!=null){
while(cur!=null){
st.push(cur);
cur = cur.left;
}
cur = st.peek();
if(cur.right==null || lastVisit==cur.right){
res.add(cur.val);
lastVisit = st.pop();
cur=null;
}else{
cur = cur.right;
}
}
return res;
}
综上我们已经说完了常规的遍历套路。可以看到前序遍历，只要一个栈。中序遍历需要一个栈和一个CUR节点。后序遍历需要一个栈，一个CUR节点，还需要一个LASTVISIT节点。
模拟系统栈的遍历方法
前序遍历
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("go",cmd.r.right));
st.push(new Command("go",cmd.r.left));
st.push(new Command("print",cmd.r));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
中序遍历
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("go",cmd.r.right));
st.push(new Command("print",cmd.r));
st.push(new Command("go",cmd.r.left));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
后序遍历
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("print",cmd.r));
st.push(new Command("go",cmd.r.right));
st.push(new Command("go",cmd.r.left));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
怎么不用栈来实现二叉树的前中后序遍历
106. Construct Binary Tree from Inorder and Postorder Traversal
首先用后序的最后一个，去把中序的队列切开。然后递归。
public TreeNode buildTree(int[] inorder, int[] postorder) {
int l = postorder.length;
if(l==0) return null;
int i=0;
for(;i<inorder.length;i++){
if(inorder[i] == postorder[l-1]) break;
}
TreeNode root = new TreeNode(postorder[l-1]);
root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
root.right = buildTree(Arrays.copyOfRange(inorder,i+1,l),Arrays.copyOfRange(postorder,i,l-1));
return root;
}
