探索Offer——JZ57：寻找二叉树中的下一个节点

问题概述

任务是基于给定的二叉树结构中的任一节点，确定并返回其在中序遍历中的直接后续节点。此二叉树的特殊之处在于，每个节点除了标准的左右子节点之外，还具有一个指向其父节点的附加属性（next指针）。

解题策略

根据中序遍历的基本原则——先左子树、再根节点、最后右子树，我们可以利用这一规则来解决问题。具体来说，可以通过分析节点的右子树和父节点关系来确定下一个访问的节点：

主要分为两种情况：

1. 如果目标节点存在右子树，则其下一个节点即为右子树中最左侧的节点；例如，在图中D的下一个节点是B，而B的下一个节点是E。

2. 若目标节点无右子树，需进一步判断其与父节点的关系：

    a) 若该节点为其父节点的左子节点，则父节点即为其下一个节点；如图中的N、I、L等节点的情况。

    b) 若该节点为其父节点的右子节点，则需向上追溯至某个节点作为其父节点的左子节点为止；若一直未找到符合条件的节点，则说明该节点已是中序遍历的最后一个节点，如图中的M节点。

实现代码

/* 定义二叉树节点结构 */ function TreeLinkNode(x) { this.val = x; this.left = null; this.right = null; this.next = null; } /* 寻找下一个节点函数 */ function GetNext(pNode) { if (!pNode) return null; // 节点为空时返回null if (pNode.right) { let temp = pNode.right; while (temp.left) { temp = temp.left; } return temp; } // 存在右子树，返回右子树最左节点 else { while (pNode.next) { if (pNode === pNode.next.left) { return pNode.next; } // 当前节点是父节点的左子节点，返回父节点 pNode = pNode.next; } return null; // 无符合条件的父节点，返回null } }

执行环境：Javascript (V8引擎)

执行耗时：10毫秒

内存消耗：5332 KB