WHCSRL 技术网

【二叉树】剑指offer 8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示,从子节点指向父节点的用虚线表示
在这里插入图片描述
在这里插入图片描述


题解

这题需要对各种情况分类讨论,一共有三种情况

  • 第一种:如果这个节点的右孩子不为空,根据中序遍历的特点,它的下一个节点是它的右孩子的最左边的孩子
    在这里插入图片描述
  • 第二种:如果这个节点是其父亲的左孩子,根据中序遍历的特点,它的下一个节点就是其父亲(注意如果父亲为null,则该节点是根节点,此时返回null
    在这里插入图片描述
  • 第三种:最复杂的一个情况,该节点为其父亲的右孩子,此时需要向上找到一个祖先节点AA是其父亲的左孩子(即回到了第二种情况),这个情况可以通过画图分析得出,例如下图中的节点4,它的下一个节点为3的父节点5,因为3是其父节点5的左孩子
    在这里插入图片描述
    在这里插入图片描述

所有代码

public class Solution {

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 1. 右孩子不空,则找到它右孩子的最左孩子
        if (pNode.right != null) {
            pNode = pNode.right;
            // 找到最左的节点
            while (pNode.left != null)
                pNode = pNode.left;
            return pNode;
        }

        TreeLinkNode parent = pNode.next;
        if (parent == null)
            return null;

        // 2. 右孩子为空,且是父亲的左孩子,父节点为下一节点
        if (parent.left == pNode)
            return pNode.next;

        // 3. 右孩子为空,且是父亲的右孩子
        while (parent != null) {
            // 向上找父亲,直到节点是其父亲的左孩子,即第二种情况
            if (parent.left == pNode)
                return parent;
            pNode = parent;
            parent = parent.next;
        }
        return null;
    }

    public static void main(String[] args) {
        TreeLinkNode r = new TreeLinkNode(1);
        r.left = new TreeLinkNode(2);
        r.left.next = r;

        TreeLinkNode pnow = r.left;
        pnow.right = new TreeLinkNode(3);
        pnow.right.next = pnow;

        pnow = pnow.right;

        pnow.right = new TreeLinkNode(4);
        pnow.right.next = pnow;
        TreeLinkNode res = new Solution().GetNext(pnow.right);
        System.out.println(res.val);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48