首頁 盲人摸象

# 题目

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

分析二叉树的下一个节点，一共有以下情况：

  1. 二叉树为空，则返回空；
  2. 节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
  3. 节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。
/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next; // 父节点
    TreeLinkNode (int x) :val (x), left (NULL), right (NULL), next (NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode->right) { // 如果有右子树，则找右子树的最左节点
            TreeLinkNode *p = pNode->right;
            while(p->left) p = p->left;
            return p;
        }
        TreeLinkNode *p = pNode;
        while(p->next) { // 没右子树，则找第一个当前节点是父节点左孩子的节点
            if(p->next->left == p) return p->next;
            p = p->next;
        }
        return nullptr; // 退到了根节点仍没找到，则返回 null
    }
};

# 复习

前序遍历：F, B, A, D, C, E, G, I, H
中序遍历：A, B, C, D, E, F, G, H, I
后序遍历：A, C, E, D, B, H, I, G, F
层次遍历：F, B, G, A, D, I, C, E, H