二叉树的下一个结点

本贴最后更新于 2450 天前,其中的信息可能已经渤澥桑田

题目描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

解题思路

中序遍历规则--》左根右。

中序遍历

所以存在两大类情况:

  • 右子树存在,下一结点就是右子树最左下结点;

  • 右子树不存在,也有两类:

    • 是父结点的左孩子,下一结点就是父结点;

    • 是父节点的右孩子,递归找父节点,直到所在树是其父结点的左子树,下一结点就是此结点。

代码

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null)
            return null;
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null)
                pNode = pNode.left;
            return pNode;
        } else {
            while (pNode.next != null && pNode.next.left != pNode)
                pNode = pNode.next;
            return pNode.next;
        }
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...