二叉树的下一个结点-根据中序遍历的特点(O(n),O(1))解题

二叉树的下一个结点

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

//解题思路
/*
       8
    6    10
   5 7  9  11
根据中序遍历的特点(O(n),O(1)):
1.pNode的右孩子为空,中序遍历顺序的下一个结点可能在其父辈root里(注意是父辈,不只是父亲)
    1.1 pNode为root的左孩子,则pNode的下一个结点为root(例如5、7、9)
    1.2 否则返回null(例如11)
2.pNode的右孩子不为空时,中序遍历顺序的下一个结点在其右子树里,此时中序遍历右子树取第一个结果即可(例如6、8、10)
 */
//犯错点
/*
  求中序遍历右子树取第一个结果即取右子树最左边的节点,不用调用inOrder()耗费运行时间
 */
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) return null;
    //1.pNode的右孩子为空,中序遍历顺序的下一个结点可能在其父辈里
    if (pNode.right == null){
        TreeLinkNode root = pNode.next;
        TreeLinkNode child = pNode;
        //1.1 pNode为root父辈的左孩子,则pNode的下一个结点为root
        while (root != null){
            if (root.left == child) return root;
            child = root;
            root = root.next;
        }
        //1.2 父辈root为空,则返回null
        return null;
    }
    //2.pNode的右孩子不为空,中序遍历顺序的下一个结点在其右子树里,此时中序遍历右子树取第一个结果即可
    TreeLinkNode rightTree = pNode.right;
    //求中序遍历右子树取第一个结果即取右子树最左边的节点
    while (rightTree.left != null){
        rightTree = rightTree.left;
    }
    return rightTree;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
1 1 评论
分享

全站热榜

正在热议