二叉树的下一个节点

ryluo 2020-06-20 14:14:23

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

注意:

样例

假定二叉树是:[2, 1, 3, null, null, null, null], 给出的是值等于2的节点。

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

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

分析:

中序遍历:左-根-右

  1. 当前节点含有右子树,那么右子树最左边的节点就是后继
  2. 当前节点没有右子树
    1. 且当前节点有父节点,并且当前节点是父节点的左节点,直接返回子节点
    2. 且当前节点有父节点,并且当前节点是父节点的有节点,沿着父节点网上找,直到当前节点是父节点的左节点。(因为若当前节点未父节点的有节点时,此时的父节点已经被遍历过了)
/**
 * 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;
        }    

        // 没有右子树
        // 1. 当前节点位父节点的左节点,直接返回父节点,需要注意前提是当前节点有父节点
        if (p->father && p == p->father->left) return p->father;

        // 2. 当前节点为父节点的右节点,沿着父节点向上找到当前节点为其父节点的左节点为止,
        // 然后返回当前节点的父节点, 需要注意前提是当前节点有父节点
        while(p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};

注意点:

在判断父节点的左节点或有节点之前一定要确保当前节点有父节点