【二叉树】重建二叉树

通过二叉树的先序和中序，或者中和后序遍历可以重建这棵二叉树。（已经先序和后序遍历并不能重构唯一的二叉树）

由先序遍历可以找出二叉树的根节点的值，再去中序/后序遍历中将节点分为左子树和右子树的节点。

一般地，有迭代和递归两种方法去重建一棵二叉树。递归比较耗时，而且确定边界时容易出错，以下代码采用迭代，时间复杂度O(n),n为树节点数。

参照先序遍历的迭代的思想，总是把左子树的左节点优先push入栈。
当栈顶元素s.top() == inorder[0]时，则说明已到达树的最左的叶子节点，随后按照先序遍历迭代思想，转向右子树。
这里设置了一个flag标志位，flag = 1转向右子树，默认flag=0持续将左子树左节点入栈。

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 //用迭代的方法替换递归
11 class Solution {
12 public:
13     struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
14         if (pre.size() == 0 || in.size() == 0)
15             return NULL;
16         stack<TreeNode *> s;
17         int i = 0; //pre的index
18         int j = 0; //in的index
19         int flag = 0; //flag = 1转向右子树
20         TreeNode *root = new TreeNode(pre[i]);
21         TreeNode *temp = root;
22         s.push(temp);
23         i++; //push一个，则i++
24         while (i < pre.size()){
25             if (!s.empty() && s.top()->val == in[j]){
26                 temp = s.top();
27                 s.pop();
28                 flag = 1;
29                 j++;
30             }else{
31                 if (flag == 0){
32                     temp->left = new TreeNode(pre[i]);
33                     temp = temp->left;
34                     s.push(temp);
35                     i++;
36                 }else{
37                     flag = 0;
38                     temp->right = new TreeNode(pre[i]);
39                     temp = temp->right;
40                     s.push(temp);
41                     i++;
42                 }
43             }
44         }
45        return root;
46     }
47 };

下面是已经中序和后序遍历，重构二叉树。

leetcode Construct Binary Tree from Inorder and Postorder

非递归思路来自于https://leetcode.com/discuss/15115/my-comprehension-of-o-n-solution-from-%40hongzhi

首先明白，后序遍历的最后一个节点的值是二叉树的根节点的值；后序遍历是左——右——根。

从后往前遍历后序和中序的节点，如果栈顶节点的值等于中序遍历尾节点，则持续将其从中序中pop_back()以及栈中pop出来，因为前面后序中已经遍历过；如果不是，则继续从后往前遍历后序节点，作为栈顶的右孩子，同时入栈。

//已知中序和后序遍历重构二叉树
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct TreeNode{
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(NULL), right(NULL){}
};

TreeNode *constructBinaryTree(vector<int> inorder, vector<int> postorder){
    if (inorder.size() == 0 || postorder.size() == 0){
        return NULL;
    }
    TreeNode *root = new TreeNode(postorder.back());
    postorder.pop_back();
    stack<TreeNode *> s;
    s.push(root);
    TreeNode *temp;
    while (1){
        if (inorder.back() == s.top()->val){
            temp = s.top(); //中序与后序相同的元素，保留最后一个根节点
            s.pop();
            inorder.pop_back();
            if (inorder.size() == 0) break; //pop完后检查inorder.size()
            if (!s.empty() && inorder.back() == s.top()->val) continue; //退出本次循环，下面语句不会执行
            temp->left = new TreeNode(postorder.back());
            postorder.pop_back();
            s.push(temp->left);
        } else{
            temp = new TreeNode(postorder.back());
            postorder.pop_back();
            s.top()->right = temp;
            s.push(temp);
        }
    }
    return root;
}

int main(){
    vector<int> inorder{4, 2, 5, 1, 3, 6};
    vector<int> postorder{4, 5, 2, 6, 3, 1};
    TreeNode *root = constructBinaryTree(inorder, postorder);
    cout << root->left->val << " " << root->right->val;
    return 0;
}