剑指offer - 二叉树的下一个节点

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e

题意

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

题解

中序遍历顺序：左-根-右。
有以下两种情况：
(1) 如果当前节点存在右子树，则返回右子树中的最靠左的节点。
(2)如果不存在右子树，则应该回溯到上一层，如果当前节点是其父节点的左儿子，则应该返回这个父节点，如果不是，一直向上回溯直到找到一个节点是其父节点的左儿子，如果已知找到树根都没有找到，说明已经遍历到最后一个节点了，返回NULL。

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
29
30
31
32
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 == NULL) return NULL;
        if(pNode->right){  //当前节点存在右子树，返回右子树中最靠左的节点
            TreeLinkNode *root = pNode->right;
            while(root->left != NULL){
                root=root->left;
            }
            return root;
        }
        TreeLinkNode * current = pNode;
        TreeLinkNode * parent = pNode->next;
        while(parent&&parent->right == current)
        {
            current = parent;
            parent = parent->next;
        }
        if(parent==NULL) //找到根节点,则返回NULL
            return NULL;
        return parent;  //找到某个节点是其父节点的左儿子
    }
};