二叉树的下一个结点

1. 题目描述

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

2. 思路

• 找到root，中序遍历
• tree.md后继节点

3. 实现

3.1. 找到root，中序遍历

type TreeLinkNode struct {
	Val   int
	Left  *TreeLinkNode
	Right *TreeLinkNode
	Next  *TreeLinkNode
}

//时间复杂度：O(N)
//空间复杂度：O(N)
func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}

	root := pNode
	for root.Next != nil {
		root = root.Next
	}

	linkNodes := make([]*TreeLinkNode, 0)
	inOrder(root, &linkNodes)
	for i := 0; i < len(linkNodes); i++ {
		if linkNodes[i] == pNode {
			if i+1 < len(linkNodes) {
				return linkNodes[i+1]
			}
		}
	}

	return nil
}

3.2. 后继节点

• go

func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}
    // 如果有右子树，找到右子树的最左节点
	current := pNode.Right
	if current != nil {
		for current.Left != nil {
			current = current.Left
		}
		return current
	}

    //如果有父节点，往上找到第一个节点，这个节点是父节点的左节点
	current = pNode
	for current.Next != nil  {
        if current.Next.Left == current {
            return current.Next
        }
        current = current.Next
	}

	return nil
}

4. 参考

• 二叉树的下一个结点_牛客网
• 面试题 04.06. 后继者 - 力扣（LeetCode）