二叉树的后序遍历 - 非递归版java实现

二叉树的后序遍历

二叉树的先序遍历 | 二叉树的中序遍历 | 二叉树的层序遍历

主要思想:首先遍历root根节点的所有左节点,并依次入栈。对出栈的元素,如果没有右儿子或者虽然有右儿子但右儿子已完成遍历,即可完成出栈;否则,再次入栈,并把右儿子入栈,遍历右儿子的所有左儿子。

版本一


import java.util.ArrayList;
import java.util.Stack;
public class Solution { 
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        /* 用来记录最新出栈的节点, * 如果当前节点的右儿子与flag相同,说明当前节点右子树已完成遍历 */
        TreeNode flag = null;
        ArrayList<Integer> ans = new ArrayList<Integer>(20);
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        while (!stack.isEmpty()) {
            cur = stack.pop();
            if (cur.right == null || cur.right == flag) {
                ans.add(cur.val);
                flag = cur;
            }
            else {
                stack.push(cur);
                cur = cur.right;
                while(cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
            }
        }
        return ans;
    }
}

版本二


import java.util.ArrayList;
import java.util.Stack;
public class Solution { 
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode prior = null;
        ArrayList<Integer> ans = new ArrayList<Integer>(20);
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (cur.right == null || cur.right == prior) {
                    ans.add(cur.val);
                    prior = cur;
                    cur = null;
                }
                else {
                    stack.push(cur);
                    cur = cur.right;
                    stack.push(cur);
                    cur = cur.left;
                }
            }
        }
        return ans;
    }
}

TreeNode的定义

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

参考文章:zhuqiuhui的专栏:Java实现二叉树后序非递归遍历(好理解)

    原文作者:cwwang15
    原文地址: https://blog.csdn.net/WANG_Chaunwang/article/details/79896631
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞