定義二叉樹數(shù)據(jù)結(jié)構(gòu)如下，其中next 指向父節(jié)點(diǎn)。傳入某個(gè)節(jié)點(diǎn)A，計(jì)算A節(jié)點(diǎn)中序遍歷結(jié)果對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)

const Node = {
  next: null,
  left: null,
  right: null,
  val: ''
}

思路

1.根據(jù)該節(jié)點(diǎn)遞歸查找根節(jié)點(diǎn)
2.根據(jù)根節(jié)點(diǎn)生成中序遍歷結(jié)構(gòu)的list
3.根據(jù)節(jié)點(diǎn)值獲取list中下一節(jié)點(diǎn)值

function findRoot( node ){
    if( !node.next ) return node;
    return findRoot( node.next )
}

function traversal( root, res = [] ) {
    if( !root ) return null;
    treval( root.left, res )
    res.push( root )
    treval( root.right, res )
    return res
}

function getNext( pNode )
{
    if( !pNode ) return null
    const root = findRoot( pNode );
    const mid = traversal( root );
    
    for( let i = 0;i < mid.length;i ++ ) {
        if( mid[ i ].val === pNode.val ) {
            return i < mid.length - 1 ? mid[ i + 1 ] : null
        }
    }
    return null
}