8. 二叉树的下一个结点

题目链接

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/**
 * 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) {}
 * };
 */

解题思路

我们先来回顾一下中序遍历的过程：先遍历树的左子树，再遍历根节点，最后再遍历右子树。所以最左节点是中序遍历的第一个节点。

① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；

② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。

 //我的代码，考虑三种情况
 /*
  //1--存在右子树 找最有一个左节点即为后续
  //2--不存在右子树，节点为左子节点 后继为父节点
  //3--不存在右子树，节点为右子节点 后继为向上遍历到一个节点为其父节点的字节点，这个节点的父节点即为后记
   //23可以兼容：考虑当前节点无右子树，判断当前节点的father是否存在 && 当前节点是否为左节点，左节点的father即为后记     
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if(!p) return nullptr;
        //--存在右子树 找最有一个左节点即为后续
        if(p->right)
        {
            p = p->right;
            while(p->left)
            {
                p = p->left;
            }
            return p;
        }
        //--不存在右子树，节点为左子节点 后继为父节点
        else if(p->father && p ==  p->father->left)
        {
            return p->father;
        }
        //--不存在右子树，节点为右子节点 后继为向上遍历到一个节点为其父节点的字节点，这个节点的父节点即为后记
        else //if(p->father && p == p->father->right)  //特殊情况 一个根节点过来，满足情况
        {
            while(p->father && p == p->father->right) p = p->father; //直到找到左节点
            return p->father;
        }
        
    }
};

//改良后的程序
//兼容了左节点情况
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }

        while (p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};

java 版本

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/

/* 二叉树的后继
          8
     6         10
   5  7      9     11
    12 13
    中序遍历： 左 根 右 [5 6 7 8   9 10 11]
    根据当前节点是否含有右子树讨论：
    （1）有右子树: 及后继节点即为右子树的最左边节点
        如6，8,右子树最左边的节点
    （2）无右子树，
        当前节点为其根节点的right：如11，13：
           返回第一个满足 当前节点的father(a:6) 是其father（b:8）的左节点的节点（b）
        当前节点为其根节点的left：如5，9：返回当前节点的根
    

*/ 
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null) {
            return null;
        }
        
        // 当前节点存在右子树,返回右子树最左侧的节点
        if(pNode.right != null) {
            TreeLinkNode p = pNode.right;
            while(p.left != null) {
                p = p.left;
            }
            return p;
        } else {
            // 当前节点为father的右节点, 找到第一次出现father是father的father的left的情况
            while(pNode.next != null && pNode.next.right == pNode) {
                pNode = pNode.next;
            }
            // 结合了当前节点是father左右节点的情况，返回父节点
            return pNode.next;
        }
    }
}