题解 | #二叉树的下一个结点#

/*class TreeLinkNode {
 *     val: number
 *     left: TreeLinkNode | null
 *     right: TreeLinkNode | null
 *     next: TreeLinkNode | null
 *     constructor(val?: number, left?: TreeLinkNode | null, right?: TreeLinkNode | null, next?: TreeLinkNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : right)
 *     }
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pNode TreeLinkNode类 
 * @return TreeLinkNode类
 */
let zIndex = []
export function GetNext(pNode: TreeLinkNode): TreeLinkNode {
    // write code here
    /** 1.首先获得根节点
    2.中序遍历
    3.存储中序遍历的结果
    4.找到中序遍历的根节点的位置，下一位就是要找到的节点
*/
        //1.获取这个节点
        let newNode = pNode
        while(newNode.next !== null){
            newNode = newNode.next
        }
        //2.中序遍历
        Inorder(newNode)
        //4.找到根节点的位置，下一位就是要找到的节点
        let index = zIndex.indexOf(pNode)
        return zIndex[index +  1]
    
}
 function Inorder(node){
        //获得左子树的节点
        if(node !== null){
            Inorder(node.left)
            zIndex.push(node)
            Inorder(node.right)
        }

}