57-二叉树的下一个节点

题⽬描述

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

复杂的节点结构如下：

public class TreeLinkNode {
	int val;
	TreeLinkNode left = null;
	TreeLinkNode right = null;
	TreeLinkNode next = null;
	
	TreeLinkNode(int val) {
		this.val = val;
	}
}

思路及解答

中序遍历获取下一个节点

第⼀种思路是先通过循环，先找到根节点，然后通过根节点，中序遍历，中序遍历的过程中，对⽐节点，是否等于输⼊的节点，然后获取下⼀个节点放回。注意没有下⼀个节点的时候，应该返回 null ，不能数组越界。

import java.util.ArrayList;
import java.util.List;

public class Solution {
	private static List<TreeLinkNode> treeLinkNodes = new ArrayList<>();
	
	public TreeLinkNode GetNext(TreeLinkNode pNode) {
		if (pNode != null) {
			TreeLinkNode root = pNode;
			// ⼀直找到根节点
			while (root != null && root.next != null) {
				root = root.next;
			}
			
			inOrder(root);
			
			for (int i = 0; i < treeLinkNodes.size(); i++) {
				if (treeLinkNodes.get(i) == pNode) {
					return i + 1 < treeLinkNodes.size() ? treeLinkNodes.get(i + 1) : null;
				}
			}
		}
		return null;
	}
	
	// 中序遍历
	public void inOrder(TreeLinkNode pNode) {
		if (pNode != null) {
			inOrder(pNode.left);
			treeLinkNodes.add(pNode);
			inOrder(pNode.right);
		}
	}
}

不借助额外的空间

上⾯的做法借助了 list ，空间复杂度是O(n) ，时间上，遍历了两次，也是O(n) 的时间复杂度。

另外⼀种做法是，不借助额外的空间，直接查找下⼀个节点。

分为⼏种情况讨论：

• 当前节点为空，直接返回空
• 当前节点不为空：
  • 如果当前节点的右节点不为空，那么下⼀个节点就是右节点的最左⼦孙节点。
  • 如果当前节点的右节点为空，那么只能到⽗节点：
    • 需要判断当前节点是不是⽗节点的左节点，如果是⽗节点的左节点，那么下⼀个节点就是⽗节点。
    • 如果当前节点不是⽗节点的左节点，那么就是⽗节点的右节点，也就是下⼀个节点应该是⽗节点的⽗节点，或者更上⼀层。这个怎么判断呢？根据当前节点是不是右节点来判断，如果是右节点，则还需要往⽗节点的上⾛⼀层，如果不是右节点，则直接放回⽗节点。

public TreeLinkNode GetNext(TreeLinkNode pNode) {
	// 右节点不为空，直接找右节点的最左⼦孙节点
	if (pNode.right != null) {
		TreeLinkNode pRight = pNode.right;
		while (pRight.left != null) {
			pRight = pRight.left;
		}
		return pRight;
	}
	
	// 右节点为空，但是当前节点是左节点，下⼀个就是其⽗节点
	if (pNode.next != null && pNode.next.left == pNode) {
		return pNode.next;
	}
		
	// 3.右节点为空，并且当前节点是右节点，那只能往上⾛
	if (pNode.next != null) {
		// 获取⽗节点
		TreeLinkNode pNext = pNode.next;
		// 判断⽗节点是不是同样是右节点，如果是，还需要往上⾛，如果不是，就可以直接放回其
		while (pNext.next != null && pNext.next.right == pNext) {
			pNext = pNext.next;
		}
		return pNext.next;
	}
	return null;
}