leetcode经典例题第六题，指定非递归来实现二叉树的后序遍历。

题目描述

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree{1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return[3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

解题思路

就是二叉树的后序遍历，它的意思是，递归程序没啥意思，要不你用非递归来实现一个？

我们知道，递归就是系统栈实现的，那么其实对于本题，我倾向于自己用一个栈来模拟系统栈，这样，无论是前序中序还是后序，改代码跟递归版本是一样，具有较强的通用性，至于另外的解法，每种都不一样，导致不好记忆。

代码提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

class Command{
    public String str;
    public TreeNode node;
    public Command(String str,TreeNode node){
        this.str = str;
        this.node = node;
    }
}

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<Command> stack = new Stack<>();
        //遇到“go”则添加左右孩子以及自己入栈
        //遇到“print”则添加进结果集
        stack.push(new Command("go",root));
        while(!stack.isEmpty()){
            Command c = stack.pop();
            if(c.str == "go"){
                //先自己
                stack.push(new Command("print",c.node));
                //再右
                if(c.node.right != null){
                    stack.push(new Command("go",c.node.right));
                }
                //再左
                if(c.node.left != null){
                    stack.push(new Command("go",c.node.left));
                }
                //出栈的顺序必然是左-右-中，即后序遍历顺序
            }else{
                res.add(c.node.val);
            }
        }
        return res;
    }
}

我们要想改成前序或者中序遍历，只需要将stack.push(new Command("print",c.node));调换一下位置即可，十分方便，这样对递归的实现原理的理解也加深了。