題⽬描述

給定⼀個⼆叉樹和其中的⼀個結點，請找出中序遍歷順序的下⼀個結點並且返回。注意，樹中的結點不僅包含左右⼦結點，同時包含指向⽗結點的指針。

複雜的節點結構如下：

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);
		}
	}
}

• 時間複雜度：O(n)。需要遍歷整棵樹（O(n)）並在列表中查找節點（最壞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;
}

• 時間複雜度：O(k)。k是到後繼節點的路徑長度，最壞情況為樹高O(h)，通常遠小於n。
• 空間複雜度：O(1)。只使用了固定數量的指針。

為了更直觀地理解這兩種情況，我們可以看一個例子。下圖中，節點 5的下一個節點是 6（對應情況1，找右子樹的最左節點），節點 7的下一個節點是 8（對應情況2，向上找到第一個作為左子節點的祖先節點的父節點）。

	  8
     / \
    6   10
   / \  / \
  5  7 9  11