题解 | #二叉树的下一个结点#

二叉树的下一个结点

http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

O(N), O(1)

  • 分类讨论,切记中序遍历,为左根右,因为需求给定结点的下一个结点,所以我们只需要讨论给定结点的右子树部分。同样扩展来说,要求给定的结点的上一个结点,只需要讨论给定结点的左子树部分

alt 分析基于题中此图

(1), pNode.right == null, 例如g结点,我们应该是沿着next往回找,且要保证往回找的结点都是遍历过的,所以加上这一判别条件,pNode.next.right == pNode,因为中序遍历-左中右,沿着next往回找的结点其实是“中”,所以是遍历过的。最后找到结点a,返回a.next即null。 可以用l结点对比来看,为什么要加那一判别条件.

(2), pNode.right != null, 例如b结点,返回以pNode.right为跟结点的子树的中序遍历的第一个结点。即是其中序遍历的下一个结点,h结点

public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {//中序遍历,左根右
    if(pNode.right == null){
        while(pNode.next != null && pNode.next.right == pNode){//mark
            pNode = pNode.next;
        }
        return pNode.next;
    }else{
        return getStart(pNode.right);
    }

}

public TreeLinkNode getStart(TreeLinkNode root){//正常中序遍历中,第一个结点
    if(root == null) return root;
    
    while(root.left != null){
        root = root.left;
    }
    
    return root;
}
}
全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗? 那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
你找工作的时候用AI吗?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
05-21 15:47
门头沟学院 Java
浪漫主义的虹夏:项目有亮点吗,第一个不是纯玩具项目吗,项目亮点里类似ThreadLocal,Redis储存说难听点是花几十分钟绝大部分人都能学会,第二个轮子项目也没体现出设计和技术,想实习先沉淀,好高骛远的自嗨只会害了自己
点赞 评论 收藏
分享
06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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