java二叉树后序遍历递归和非递归实现

KLQ 2020-07-14 14:48:02 java常见问答 4203

之前给大家介绍了java二叉树前序遍历和中序遍历递归和非递归的实现,接下来要给大家介绍的就是java二叉树后序遍历的递归以及非递归的实现的内容。

java二叉树

访问顺序-左子树-右子树-根节点。

上图的访问结果-AEFDHZMG。

1、递归实现

public void postOrderTraverse(TreeNode root)
{
    if (root != null)
    {
        postOrderTraverse(root.left);
        postOrderTraverse(root.right);
        System.out.print(root.val + "->");
    }
}

2、非递归实现

public void postOrderTraverse(TreeNode root)
{
    TreeNode cur, pre = null;
    Stack < TreeNode > stack = new Stack < > ();
    stack.push(root);
    while (!stack.empty())
    {
        cur = stack.peek();
        if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right)))
        {
            System.out.print(cur.val + "->");
            stack.pop();
            pre = cur;
        }
        else
        {
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }
}

对于java二叉树后序遍历的递归以及非递归实现你都清楚了吗?更多相关内容,请继续关注奇Q工具网的java实例栏目来进行了解吧。

推荐阅读:

java二叉树前序遍历递归和非递归实现

java二叉树中序遍历递归和非递归实现

java二叉树深度不用递归,非递归实现