[AcWing]19. 二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

  • 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
  • 二叉树一定不为空，且给定的节点一定不是空节点；

数据范围

树中节点数量[0,100]。

样例

1
2
3
4
5
6
7
8
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3

算法思路

中序遍历：左根右

情况1：有右子树

情况2：无右子树

image-20230407214109154

image-20230407215844606

image-20230407220425944

image-20230407221400823

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        // 如果它有右子树，找到右子树下的最左边的节点
        if(p -> right){
            p = p -> right;
            while(p -> left) p = p -> left;
            return p;
        }
        
        // 如果它没有右子树，则寻找它的父亲节点，直到满足条件p == p -> father -> left
        // 那么 p -> father 就是 它的中序遍历的下一个节点
        while(p -> father && p != p -> father -> left) p = p -> father;
        return p -> father;
    }
};

时间复杂度

不论往上找还是往下找，总共遍历的节点数都不大于树的高度。所以时间复杂度是`O(h)`，其中 h 是树的高度。