本文共 1722 字，大约阅读时间需要 5 分钟。

题目描述

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

分析

二叉树的中序遍历结构是“左根右”的顺序。要定位一个节点的而下一个节点有3中情况需要考虑：

结构如图：虚线表示指向父节点的指针。

1. 如果一个节点具有右子树，则它的下一个节点就是它的右子树中的最左子节点。例如，a的下一个节点是f，b的下一个节点是h。
2. 如果一个节点没有右子树并且它是父亲节点的左子节点，则它的下一个节点就是父亲节点。例如，d的洗衣歌节点是b，f的下一个节点是c。
3. 如果一个节点没有右子树并且它是父亲节点的右子节点，则比较复杂：需要沿着父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。 例如i的下一个节点是a。

牛客AC：

/*public class TreeLinkNode {    int val;    TreeLinkNode left = null;    TreeLinkNode right = null;    TreeLinkNode next = null;    TreeLinkNode(int val) {        this.val = val;    }}*/public class Solution {
       public TreeLinkNode GetNext(TreeLinkNode pNode) {        if (pNode == null)            return null;        TreeLinkNode pNext = null;  // 需要寻找的下一个节点        if (pNode.right != null) {            // 当前节点有右子树，它的下一个节点就是它的右子树中的最左子节点            TreeLinkNode pRight = pNode.right;            while (pRight.left != null)     // 寻找右子树中的最左子节点                pRight = pRight.left;            pNext = pRight;        } else if (pNode.next != null) {            TreeLinkNode pCurrent = pNode;            TreeLinkNode pParent = pNode.next;            // 当前节点没有右子树,是父亲节点的左子节点，它的下一个节点就是父亲节点。            if (pParent != null && pCurrent == pParent.left)                pNext = pParent;            else {                // 当前节点没有右子树,是父亲节点的右子节点：                // 沿着父节点指针一直向上遍历，找到一个是它父节点的左子节点的节点。                // 如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。                while (pParent != null && pCurrent == pParent.right) {                    pCurrent = pParent;                    pParent = pParent.next;                }                pNext = pParent;            }        }        return pNext;    }}

参考