非递归遍历二叉树

题目 (LeetCode #94, #144, #145)

先序遍历

利用栈实现二叉树的非递归遍历, 先将头结点放入栈中, 若栈不为空则一直循环, 弹出栈中元素, 若弹出的元素含有子节点则将子元素按先右后左的顺序压入栈中, 直到所有节点全部弹出.

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);

            TreeNode tmp;
            while (!stack.isEmpty()) {
                tmp = stack.pop();
                result.add(tmp.val);

                if (tmp.right != null) {
                    stack.push(tmp.right);
                }

                if (tmp.left != null) {
                    stack.push(tmp.left);
                }
            }
        }

        return result;
    }
}

Python

class PreorderTraversal:
    def preorder_traversal(self, root):
        result = []
        
        if root:
            stack = []
            stack.append(root)
            
            while stack:
                tmp = stack.pop()
                result.append(tmp.val)
                
                if tmp.right: stack.append(tmp.right)
                if tmp.left: stack.append(tmp.left)
        
        return result

后序遍历

后序遍历可仿照先序遍历, 改变左右子树入栈顺序, 即先入栈左子树, 后入栈右子树, 以实现中右左依次出栈. 出栈时, 先将出栈元素放入另一个辅助栈中, 再全部依次出栈, 这样即实现了对每棵子树的逆序, 即最终为左右中的后序遍历顺序.

Java

public class PostorderTraversal {
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> help = new Stack<>();
            stack.add(root);

            TreeNode tmp;
            while (!stack.isEmpty()) {
                tmp = stack.pop();
                help.push(tmp);

                if (tmp.left != null) {
                    stack.push(tmp.left);
                }

                if (tmp.right != null) {
                    stack.push(tmp.right);
                }
            }

            while (!help.isEmpty()) {
                result.add(help.pop().val);
            }
        }

        return result;
    }
}

Python

class PostorderTraversal:
    def postorder_traversal(self, root):
        result = []
        
        if root:
            stack = []
            help_stack = []
            stack.append(root)
            
            while stack:
                tmp = stack.pop()
                help_stack.append(tmp.val)
                
                if tmp.left: stack.append(tmp.left)
                if tmp.right: stack.append(tmp.right)
            
            while help_stack:
                result.append(help_stack.pop())
        
        return result

中序遍历

先将左边界全部压入栈中, 再逐级向上弹出, 弹出过程中若该节点的左子树不为 null 则压入该左子树的边界.

Java

public class InorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    result.add(root.val);
                    root = root.right;
                }
            }
        }

        return result;
    }
}

Python

class InorderTraversal:
    def inorder_traversal(self, root):
        result = []

        if root:
            stack = []

            while stack or root:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    root = stack.pop()
                    result.append(root.val)
                    root = root.right

        return result