剑指Offer57 二叉树的下一个节点

Java 题解

     a
    / \
   b   c
  / \ / \
 d  e f  g
   / \
  h   i

情形 1

如果一个节点有右子树,那么他的下一个节点就是他的右子树的最左子节点(从右子节点出发一直沿着指向左子节点的指针就能找到他的下一个子节点),如:a的下一个节点就是d。

情形 2

如果一个节点没有右子树,且此节点是他的父节点的左子节点,他的下一个节点就是他的父节点,如:节点d的下一个节点是b。

情形 3

如果一个节点既没有右子树,且此节点又是父节点的右子节点。我们可以沿着此节点指向父节点的指针一直向上遍历,直到找到一个是他父节点的左子节点的节点,如:i节点的下一个节点,沿着他的父节点的指针遍历,先到达e,但是e是他父节点b的右子节点,所以继续向上,到达b节点,b是他父节点a的左子节点,所以i的下一个节点是a。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null)
            return null;

        TreeLinkNode pNext = null;

        // 情形 1
        // 如果一个节点有右子树,那么他的下一个节点就是他的右子树的最左子节点
        // (从右子节点出发一直沿着指向左子节点的指针就能找到他的下一个子节点)
        if(pNode.right != null){
            TreeLinkNode pRight = pNode.right;
            while(pRight.left!=null){
                pRight = pRight.left;
            }
            pNext = pRight;
        }else if(pNode.next != null){
            // 情形 2
            // 如果一个节点没有右子树,且此节点是他的父节点的左子节点,他的下一个节点就是他的父节点
            if(pNode.next.left == pNode){
                pNext = pNode.next;
            }

            // 情形3
            // 如果一个节点既没有右子树,且此节点又是父节点的右子节点。
            // 我们可以沿着此节点指向父节点的指针一直向上遍历,直到找到一个是他父节点的左子节点的节点,
            else {
                TreeLinkNode curr = pNode;
                TreeLinkNode pParent = pNode.next;
                while(pParent!=null && curr == pParent.right){
                    curr = pParent;
                    pParent = pParent.next;
                }
                pNext = pParent;
            }

        }
        return pNext;
    }
}
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务