• 二叉树的下一个结点
    • 题目
    • 解题思路

    二叉树的下一个结点

    题目

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

    解题思路

    考虑以下二叉树:

    image

    其中序遍历的结果是:d,b,h,e,i,a,f,c,g

    1. 当前节点有右子树:右子树的最左节点 — b 节点
    2. 当前节点无右子树并且为父节点的左子树:父节点 — d 节点
    3. 当前节点无右子树并且为父节点的右子树:第一个祖先节点为左节点的节点 — i 节点
    1. public TreeLinkNode GetNext(TreeLinkNode pNode) {
    2. if (pNode == null) return null;
    3. TreeLinkNode parent = pNode.next;
    4. if (pNode.right == null) {
    5. if (parent == null) {
    6. return null;
    7. }
    8. //右节点
    9. if (parent.right == pNode) {
    10. TreeLinkNode cursor = parent;
    11. while (true) {
    12. TreeLinkNode p = cursor.next;
    13. if (p == null) return null;
    14. if (cursor == p.left) return p;
    15. cursor = p;
    16. }
    17. } else {
    18. return parent;
    19. }
    20. } else {
    21. TreeLinkNode cursor = pNode.right;
    22. while (cursor.left != null) {
    23. cursor = cursor.left;
    24. }
    25. return cursor;
    26. }
    27. }