【剑指offer】面试题08 - 二叉树的下一个节点

朴灿烈づ我的快乐病毒、 2022-11-04 12:25 106阅读 0赞

### 文章目录 ###

*  面试题 8：二叉树的下一个节点
 *   *  解法一：递归解法
     *  解法二：使用辅助数组

# 面试题 8：二叉树的下一个节点 #

题目描述

> 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
> 
> 题目链接：[牛客网][Link 1]

## 解法一：递归解法 ##

> 思路：
> 
> 1.  该结点有右子树，则在右子树中寻找最左侧节点，便是该节点的下一个节点
> 2.  该结点没有右子树：
> 
>  *  该结点是父节点的左子树，则该结点的父节点便是该结点的下一个节点
>  *  该结点是父节点的右子树，使用两个指针：cur 指向当前节点，parent 指向 cur 的父节点，迭代寻找直到 cur 是 parent 的左子树为止，找到后返回 parent ，找不到便返回 NULL

TreeLinkNode* GetNext(TreeLinkNode* node) { 
        if(node == nullptr) return node;
        TreeLinkNode* nextNode = nullptr;
        if(node->right != nullptr)
        { 
            nextNode = node->right;
            while(nextNode->left != nullptr)
            { 
                nextNode = nextNode->left;
            }
        }
        else if(node->next != nullptr)
        { 
            nextNode = node;
            TreeLinkNode* parent = node->next;
            while(parent != nullptr && nextNode == parent->right)
            { 
                nextNode = parent;
                parent = parent->next;
            }
            nextNode = parent;
        }
        return nextNode;
    }

## 解法二：使用辅助数组 ##

> 思路：
> 
> 1.  寻找到 root 节点
> 2.  将中序遍历的结果放入一个 vector 中
> 3.  遍历 vector 寻找该节点的下一个节点

class Solution { 
    public:
        TreeLinkNode* GetNext(TreeLinkNode* node) { 
            if(node == nullptr) return nullptr;
            TreeLinkNode* root = node;
            while(root->next)
                root = root->next;
            inorder(root);
            int position = 0;
            for(int i = 0; i < v.size(); i++)
                if(v[i] == node)
                { 
                    position = i;
                    break;
                }
            if(position == v.size() - 1)
                return nullptr;
            return v[position + 1];
        }
    private:
        vector<TreeLinkNode*> v;
        void inorder(TreeLinkNode*& node)
        { 
            if(node == nullptr)
                return;
            inorder(node->left);
            v.push_back(node);
            inorder(node->right);
        }
    };

[Link 1]: https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey