FindTreeNode

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/31/]

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

注意：

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

样例

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

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

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

算法描述

分两种情况讨论

  • 当p.right!=null，一直找有子树的左子树，直到左子树的左子树为空，返回当前结点；
  • 当p.right==null，需要找到该节点的父节点，如果p==p.father.right，那么当前结点的后继就是p.father.father;

C++代码

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
27
28
/**
 * 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)
            return LCR(p->right);
        else {
             while(p->father&&p == p->father->right)p  = p->father;
            return p->father;
        }
    }
    
    TreeNode* LCR(TreeNode* root){
        while(root->left!=NULL){
            root = root->left;
        }
        return root;
    }
};

Java代码

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
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode father;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        if(p.right!=null){
            return LCR(p.right);
        }else {
            while(p.father!=null&&p==p.father.right)p=p.father;
            return p.father;
        }
    }
    
    public TreeNode LCR(TreeNode p){
        
        while(p.left!=null){
            p=p.left;
        }
        return p;
    }
}