非递归实现二叉树遍历

前、中、后序遍历改动都很小

前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 /**
  非递归实现二叉树遍历
  */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while( !stack.isEmpty()) {
            Command command = stack.pop();
            if(command.s.equals("print")) {
                res.add(command.node.val);
            } else {
                if(command.node.right != null) {
                    stack.push(new Command("go", command.node.right));
                }
                if(command.node.left != null) {
                    stack.push(new Command("go", command.node.left));
                }
              // 只需移动该语句位置，即可实现中、后序遍历
                stack.push(new Command("print", command.node));
            }
        }

        return res;
    }
}

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

中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 /**
  非递归实现二叉树遍历
  */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while( !stack.isEmpty()) {
            Command command = stack.pop();
            if(command.s.equals("print")) {
                res.add(command.node.val);
            } else {
                if(command.node.right != null) {
                    stack.push(new Command("go", command.node.right));
                }
              //中序遍历
                stack.push(new Command("print", command.node));
                if(command.node.left != null) {
                    stack.push(new Command("go", command.node.left));
                }
                
            }
        }

        return res;
    }
}

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

后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 /**
  非递归实现二叉树遍历
  */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while( !stack.isEmpty()) {
            Command command = stack.pop();
            if(command.s.equals("print")) {
                res.add(command.node.val);
            } else {
              //后序遍历
                stack.push(new Command("print", command.node));
                if(command.node.right != null) {
                    stack.push(new Command("go", command.node.right));
                }
                
                if(command.node.left != null) {
                    stack.push(new Command("go", command.node.left));
                }
                
            }
        }

        return res;
    }
}

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

Q.E.D.