剑指offer 面试题8：二叉树的下一个节点（中序遍历）java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer 面试题8：二叉树的下一个节点（中序遍历）java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1052字，纯文字阅读大概需要2分钟。

内容图文

public class BinaryTreeGetNext {
    public static void main(String args[]) {
        getNext(new BinaryTreeNode(3));
    }

    private static BinaryTreeNode getNext(BinaryTreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        BinaryTreeNode mNext = null;
        // 有右子树
        if (treeNode.right != null) {
            BinaryTreeNode mRight = treeNode.right;
            while (mRight.left != null) {
                mRight = mRight.left;
            }
            mNext = mRight;
        }
        // 没有右子树
        else if (treeNode.parent != null) {
            BinaryTreeNode mCurNode = treeNode;
            BinaryTreeNode mParNode = mCurNode.parent;
            while (mParNode != null && mCurNode == mParNode.right) {
                mCurNode = mParNode;
                mParNode = mParNode.parent;
            }
            mNext = mParNode;
        }
        return mNext;
    }

    private static class BinaryTreeNode {
        int val;
        BinaryTreeNode left;
        BinaryTreeNode right;
        BinaryTreeNode parent;

        BinaryTreeNode(int val) {
            this.val = val;
        }
    }
}

要点提示：

• 1、在当前节点有右子树的情况下，循环遍历右子树的左子节点及其子节点的左子节点
• 2、没有右子树的情况，判断循环结束的关键在于在当前节点父节点非空且当前节点是否等于其父节点的右子节点
• 3、当前节点等于其父节点的右子节点 表明要继续向上遍历父节点，否则遍历结束

内容总结

以上是互联网集市为您收集整理的剑指offer 面试题8：二叉树的下一个节点（中序遍历）java全部内容，希望文章能够帮你解决剑指offer 面试题8：二叉树的下一个节点（中序遍历）java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---