二叉树的下一个结点
题目描述
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
示例
代码
代码1 先找到二叉树的根，然后中序遍历，将结果保存到数组中，然后在数组中找到下一节点
js
/*
这个题一定要认真读题，给的是二叉树的其中一个节点，但是略微不同，节点记录了父节点的引用
所以我们可以根据这个引用找到树的根节点，然后中序遍历根节点，找到给出节点中序遍历后的下一节点
1. 找到树的根节点
2. 中序遍历根节点，将结果保存到一个数组中
3. 从数组中比对，找到传入节点的下一节点
*/
function GetNext(pNode)
{
// 找到根节点
let vRoot = pNode
while(vRoot.next){
vRoot = vRoot.next
} // 找到了
let tempArr = [] // 存储中序遍历结果
// 中序遍历，将结果保存到数组中
inOrder(vRoot)
// 开始从数组中找
let i = 0
for(; i < tempArr.length; i++){
if(tempArr[i] === pNode) { // 找到了
break
}
}
// 如果找到的是最后一个节点，或者直接遍历完事都没有找到，返回null
if(i === tempArr.length-1 || i === tempArr.length ) return null
return tempArr[i+1] // 返回下一节点
function inOrder(vRoot){
if(!vRoot) return
inOrder(vRoot.left)
tempArr.push(vRoot)
inOrder(vRoot.right)
}
}时间复杂度O(n)：递归的节点数 空间复杂度O(n)：数组保存的节点数
代码2 分情况直接找
js
/*
直接找
1. 如果有右子树，下一节点是右子树的最左节点，如果找不到最左节点，那就是右子树这个节点
2. 没有右子树时，
2.1 在某一父节点的左子树上，那下一节点就是这个父节点
2.2 在某一父节点的右子树上，就一直顺着这个父节点往上找，直到找到某个节点是父节点的左子树，如果存在，这个节点就是下一节点
剩余情况就返回null
*/
function GetNext(pNode)
{
// 1. 有右子树，下一节点就是右子树的最左节点
if(pNode.right){
let node = pNode.right
// 找它的最左节点
while(node.left){ // 如果没有左节点，那这个节点就是下一节点，如果有，就找最左节点
node = node.left
}
return node
}
// 2.1 没有右子树，为某一父节点的左子树
if(!pNode.right && pNode.next && pNode.next.left === pNode){
// 那么这个父节点就是下一节点
return pNode.next
}
// 2.2 没有右子树，为某一父节点的右子树
if(!pNode.right && pNode.next && pNode.next.right === pNode){
// 沿着父节点一直往上找，直到找到某一个节点是他父节点的左子树时，下一节点就是结果
let node = pNode.next
while(node.next && node.next.right === node ){
node = node.next
}
return node.next
}
return null // 其他情况，返回null
}时间复杂度O(n)：最坏的情况是一条链表，直接往上会找n次
空间复杂度O(1)：并未有任何的其他开销，全部在原来的链表上操作的。