剑指offer-57、二叉树的下一个节点

题⽬描述

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

1. public class TreeLinkNode {
2.         int val;
3.         TreeLinkNode left = null;
4.         TreeLinkNode right = null;
5.         TreeLinkNode next = null;
6.        
7.         TreeLinkNode(int val) {
8.                 this.val = val;
9.         }
10. }

复制代码

思路及解答

中序遍历

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

1. import java.util.ArrayList;
2. import java.util.List;
4. public class Solution {
5.         private static List<TreeLinkNode> treeLinkNodes = new ArrayList<>();
6.        
7.         public TreeLinkNode GetNext(TreeLinkNode pNode) {
8.                 if (pNode != null) {
9.                         TreeLinkNode root = pNode;
10.                         // ⼀直找到根节点
11.                         while (root != null && root.next != null) {
12.                                 root = root.next;
13.                         }
14.                        
15.                         inOrder(root);
16.                        
17.                         for (int i = 0; i < treeLinkNodes.size(); i++) {
18.                                 if (treeLinkNodes.get(i) == pNode) {
19.                                         return i + 1 < treeLinkNodes.size() ? treeLinkNodes.get(i + 1) : null;
20.                                 }
21.                         }
22.                 }
23.                 return null;
24.         }
25.        
26.         // 中序遍历
27.         public void inOrder(TreeLinkNode pNode) {
28.                 if (pNode != null) {
29.                         inOrder(pNode.left);
30.                         treeLinkNodes.add(pNode);
31.                         inOrder(pNode.right);
32.                 }
33.         }
34. }

复制代码

• 时间复杂度：O(n)。需要遍历整棵树（O(n)）并在列表中查找节点（最坏O(n)）。
  
• 空间复杂度：O(n)。
  

不借助额外的空间(推荐)

据中序遍历的顺序规则和节点的位置关系，通过指针操作直接定位。
核心思路：中序遍历的顺序是“左-根-右”。给定节点的“下一个节点”取决于它自己的位置情况
分为⼏种情况讨论：

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

1. public TreeLinkNode GetNext(TreeLinkNode pNode) {
2.         // 右节点不为空，直接找右节点的最左⼦孙节点
3.         if (pNode.right != null) {
4.                 TreeLinkNode pRight = pNode.right;
5.                 while (pRight.left != null) {
6.                         pRight = pRight.left;
7.                 }
8.                 return pRight;
9.         }
10.        
11.         // 右节点为空，但是当前节点是左节点，下⼀个就是其⽗节点
12.         if (pNode.next != null && pNode.next.left == pNode) {
13.                 return pNode.next;
14.         }
15.                
16.         // 3.右节点为空，并且当前节点是右节点，那只能往上⾛
17.         if (pNode.next != null) {
18.                 // 获取⽗节点
19.                 TreeLinkNode pNext = pNode.next;
20.                 // 判断⽗节点是不是同样是右节点，如果是，还需要往上⾛，如果不是，就可以直接放回其
21.                 while (pNext.next != null && pNext.next.right == pNext) {
22.                         pNext = pNext.next;
23.                 }
24.                 return pNext.next;
25.         }
26.         return null;
27. }

复制代码

• 时间复杂度：O(k)。k是到后继节点的路径长度，最坏情况为树高O(h)，通常远小于n。
  
• 空间复杂度：O(1)。只使用了固定数量的指针。
  

为了更直观地理解这两种情况，我们可以看一个例子。下图中，节点 5的下一个节点是 6（对应情况1，找右子树的最左节点），节点 7的下一个节点是 8（对应情况2，向上找到第一个作为左子节点的祖先节点的父节点）。

1.           8
2.      / \
3.     6   10
4.    / \  / \
5.   5  7 9  11

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！