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

KLQ 2020-07-14 15:04:54 java常见问答 5038

下面给大家分享的是一个使用非递归的方法,中序遍历二叉树的实例,对于这个方面感兴趣的朋友可以来了解一下哦。

要求:

非递归,中序遍历二叉树。

分析:

前序遍历,这里可以用一个栈来模拟一下操作,首先的话先将root压栈,每一次从堆栈当中弹出栈顶元素,就表示当前访问的元素,对其进行打印,依次判断,它的右子树和左子树是否非空,并进行压栈操作,先压栈右子树。

那么为什么要先压栈右子树呢?

这里的话主要就是因为先压栈的后弹出,左子树需要先访问,所以,左子树就后压栈。

中序遍历和后序遍历就要更加的复杂一些。

代码:

public class Solution
{
    // 非递归中序遍历
    public List < Integer > inorderTraversal(TreeNode root)
    {
        List < Integer > res = new ArrayList < > ();
        IF(root == null)
        {
            return res;
        }
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode p = root;
        while (p != null || !stack.isEmpty())
        {
            if (p != null)
            {
                stack.push(p);
                p = p.left;
            }
            else
            {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }
    // 非递归后序遍历
    public List < Integer > postorderTraversal(TreeNode root)
    {
        List < Integer > res = new ArrayList < > ();
        if (root == null)
        {
            return res;
        }
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode p = root;
        // 标记最近出栈的节点,用于判断是否是p节点的右孩子,如果是的话,就可以访问p节点
        TreeNode pre = p;
        while (p != null || !stack.isEmpty())
        {
            if (p != null)
            {
                stack.push(p);
                p = p.left;
            }
            else
            {
                p = stack.pop();
                if (p.right == null || p.right == pre)
                {
                    res.add(p.val);
                    pre = cur;
                    p = null;
                }
                else
                {
                    stack.push(p);
                    p = p.right;
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        return res;
    }
    // 非递归层次遍历
    public List < Integer > levelTraversal(TreeNode root)
    {
        List < Integer > res = new ArrayList < > ();
        if (root == null)
        {
            return res;
        }
        Queue < TreeNode > queue = new LinkedList < > ();
        q.add(root);
        while (!queue.isEmpty())
        {
            // current node
            TreeNode current = queue.remove();
            res.add(current.val);
            if (current.left != null)
            {
                queue.add(current.left);
            }
            if (current.right != null)
            {
                queue.add(current.right);
            }
        }
        return res;
    }
}

以上内容源于网络,仅供参考,希望可以对你有所帮助。

假如,你还想了解更多的java实例,可以继续的关注奇Q工具网,有更多经典实例可以为你分享。

推荐阅读:

java二叉树层次遍历(实例)

将二叉树变换为源二叉树的镜像如何实现?思路和实现

从上往下打印出二叉树的每个节点(思路和实现)