[数据结构与算法]leetcode-重建二叉树-83

题目要求

代码实现

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <stack>
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
        //判断特殊情况
        if(pre.size() == 0 || in.size() == 0)
        {
            return nullptr;
        }
        
        stack<TreeNode*> st;//栈
        int preIndex = 0;//前序遍历下标
        int inIndex = 0;//中序遍历下标
        //处理树的根节点
        TreeNode* root = new TreeNode(pre[preIndex]);//确定根节点
        st.push(root);
    
        //遍历 前序遍历数组，生成对应的根节点
        for(preIndex = 1; preIndex < pre.size(); preIndex++)
        {
            TreeNode* node = st.top();
            //之前压栈的元素 不等于 中序遍历数组中开头的数
            if(node->val != in[inIndex])
            {
                node->left = new TreeNode(pre[preIndex]);
                st.push(node->left);
            }
            else
            {
                while(!st.empty() && st.top()->val == in[inIndex])
                {
                    node = st.top();
                    st.pop();
                    inIndex++;
                }
                node->right = new TreeNode(pre[preIndex]);
                st.push(node->right);
            }
        }
    
        return root;
    }
};