[数据结构与算法]Java-非递归实现二叉树前、中、后序遍历

迭代实现前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root != null || !stack.isEmpty()) {
        	// 初始时，先将这棵树的所有最左侧的节点入栈，并添加到list中（因为是先序遍历）
            while(root != null){
                stack.push(root);
                list.add(root.val);
                root = root.left;
            }
            // 此时root已经为空，获取栈顶元素，就是最后一个入栈的左侧节点
            root = stack.pop();
            // 如果栈顶元素的右节点不为空，那么就指向右节点
            if(root.right != null) {
                root = root.right;
            }else{
            // 如果栈顶元素右节点为空，此时当前节点已经被添加过list中了，所以，将他设置为空，然后等待新的栈顶元素赋给他
                root = null;
            }
        }
        return list;
    }

迭代实现中序遍历

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

迭代实现后序遍历

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    if(root == null) return list;
    // 栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode pre = null;
    while(root != null || !stack.isEmpty()) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
        // 说明上一个节点的左子树为空
        root = stack.pop();
        // 然后判断右子树,如果右子树为空或者右子树已经遍历过
        if(root.right == null || root.right == pre) {
            list.add(root.val);
            pre = root;
            root = null;
        }else{
            // 如果还有右子树，那就遍历右子树
            stack.push(root);
            root = root.right;
        }
    }
    return list;
}

阅读世界，共赴山海

423全民读书节，邀你共读