题解 | #重建二叉树#

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

思路

题目分析

题目给出了我们两个数组，一个前序遍历数组，一个中序遍历数组

我们需要返回构建的一棵树，返回其根节点

我们要明确的是
- 前序先按照索引顺序取值，取到的值去找在中序序列中的位置pos
- pos将中序序列分为左右两边，分别代表左子树的范围和右子树的范围
- 根据pos分割的结果确定前序中剩下部分如何分割左子树和右子树
- 因此很容易形成递归的想法

方法一：递归

方法一：递归（推荐）
- 我们设计递归函数代表返回建立好的树的根节点
- 设计递归函数的的参数包括（pre，vin，前序首，前序尾，中序首，中序尾）
- 因此我们第一次在reConstructBinaryTree()函数中调用时应该传入的前序首中序首都是0，前序尾中序尾都是0
- 在递归函数体内部
  - 首先判断边界是否合法，不合法直接返回NULL
  - 然后前序取值直接作为根节点head
  - 并以该值找到中序序列中的位置pos
  - 从pos进行分割左右子树，进一步递归
  - head->left = 递归左子树，传入必要的前序后序序列，并传入新的左子树、右子树的范围界限
  - head->right = 递归右子树，传入必要的前序后序序列，并传入新的左子树、右子树的范围界限
  - 最终返回根节点

alt


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int l, r;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        l = 0;                                        // 首先定位整个序列的首尾
        r = pre.size() - 1;
        return build(pre, vin, l, r, l, r);
    }
    
    TreeNode* build(vector<int>& pre, vector<int>& vin, int pl, int pr, int il, int ir){
        if(pl > r || ir > r || pl > pr || il > ir) return NULL;            // 判断边缘条件直接返回
        int num = pre[pl];                                                 // 从pre中每次前面读取一个数字
        TreeNode* head = new TreeNode(num);                                // 构成一个节点
        vector<int>::iterator iter = find(vin.begin(), vin.end(), num);    // 根据这个数字定位在中序vin中的位置
        int pos = iter - vin.begin();                                      // 计算出下标值
        if(pos > ir) return NULL;                                          // 同样判断是否越界
        head->left = build(pre, vin, pl+1, pl+pos-il, il, pos-1);          // 左子节点递归，其中第三、第四个参数是下一轮前序遍历的首尾，第五第六个参数是中序遍历的首尾
        head->right = build(pre, vin, pl+1+pos-il, pr, pos+1, ir);         // 右子节点递归
        return head;
    }
};

复杂度分析

时间复杂度： $O (n l o g n)$ ，遍历了所有节点，并且在遍历节点的时候需要调用find函数，find的时间代价范围又和截取界限有关，也和树的结构有关
空间复杂度： $O (n)$ ，重建树的所有节点所占用的空间开销为 $O (n)$ 级别

方法二：迭代

方法二：迭代
- 首先我们明确在前序序列中，相邻的两个元素u和v在树中的位置关系
- v节点
  - （情况1）一定是u的左子节点
  - （情况2）或者当u无左子节点，v是uoru某祖先节点的右子节点
- 因此我们首先要做的是顺着前序序列，一路将前序序列往左下方向走的这一路节点全部压栈，可以建立和左子节点的关系。
- 压到停止的规则是：压到最深处的时候，此时节点正好是中序的开始，因此当发现中序开始和我们前序压入的值相同的时候，停止压栈
- 此时发现中序遍历的前几个节点其实就是栈中刚刚从栈顶往栈底看的几个节点
- 此时是符合（情况2）
- 我们循环退栈，直到栈顶元素和中序序列的节点对应不同为止
- 现在我们找到了（情况2）中的两个节点关系，可以建立和右子节点的关系。
- 再将这个右子节点压栈，重复以上的过程


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0) return NULL;            // 特殊情况vector为空直接返回NULL
        TreeNode* root = new TreeNode(pre[0]);      // 先标记第一个pre的元素为根节点
        stack<TreeNode*> s;
        s.push(root);                               // 栈中压入根节点，准备根据前序遍历左下方向的节点都入栈准备
        int pos = 0;                                // 代表中序遍历中我们要找的元素目标下标，中序中pos指向的值为前序遍历节点直到左子节点为空时的节点值
        for(int i = 1; i < pre.size(); i++) {
            int curNum = pre[i];                    // 继续根据pre列表拿值
            TreeNode* node = s.top();
            if(node->val != vin[pos]) {             // 判断栈顶节点值是否和中序指向的值相同
                node->left = new TreeNode(curNum);  // 如果不同则说明前序遍历忘左下方向的节点还没访问完
                s.push(node->left);                 // 要继续访问完
            }
            else {                                  // 如果栈顶和中序pos指向的值一致后
                while(!s.empty() && s.top()->val == vin[pos]) {    // 此时栈中压入的前序和中序pos右移指向的两个节点是沿着路径反向相同搞得
                    node = s.top();
                    s.pop();
                    pos++;
                }
                node->right = new TreeNode(curNum); // 直到栈顶和中序指向值不同时退出循环，此时的pre指向的元素是node节点的右子节点
                s.push(node->right);                // 然后继续压入右子节点重复以上的过程
            }
        }
        return root;
    }
};