根据二叉树的前序和中序遍历结果构造二叉树¶

Leetcode 105.从前序与中序遍历序列构造二叉树
前序的第一个为根，在中序中找到根的位置。
中序中根的左右两边即为左右子树的中序遍历。同时可知左子树的大小size-left。
前序中根接下来的size-left个是左子树的前序遍历。
由此可以递归处理左右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = preorder.size(), n = inorder.size();
        return build(0, m, 0, n, preorder, inorder);
    }

    TreeNode *build(int pre_start, int pre_end, int in_start, int in_end, vector<int>& preorder, vector<int>& inorder)
    {
        if (pre_start == pre_end || in_start == in_end) return NULL;

        TreeNode *root = new TreeNode(preorder[pre_start]);
        int pos = in_start;
        for (int i = in_start; i < in_end; ++i) {
            if (inorder[i] == preorder[pre_start]) {
                pos = i; break;
            }
        }
        int leftSize = pos - in_start;

        root -> left = build(pre_start + 1, pre_start + 1 + leftSize, in_start, pos, preorder, inorder);
        root -> right = build(pre_start + 1 + leftSize, pre_end, pos + 1, in_end, preorder, inorder);
        return root;
    }
};

一本通-1366：二叉树输出(btout)

题目的意思是要根据每个节点的长度然后前序遍历输出，关键点在于如何确定节点长度。在二叉树的每个节点额外保存一个频率信息freq，首先是根据前序和中序遍历结果建树，然后递归的去计算节点的频率信息，最后递归实现前序遍历即可。

#include <bits/stdc++.h>

using namespace std;

string preorder, inorder;

struct TreeNode
{
    char ch;
    int freq;
    TreeNode *left, *right;
    TreeNode(char x): ch(x), freq(0), left(NULL), right(NULL) {}
};


TreeNode *build(int pre_start, int pre_end, int in_start, int in_end)
{
    if (pre_start == pre_end || in_start == in_end) return NULL;

    TreeNode *root = new TreeNode(preorder[pre_start]);
    int pos = inorder.find(preorder[pre_start]);
    int leftSize = pos - in_start;

    root -> left = build(pre_start + 1, pre_start + 1 + leftSize, in_start, pos);
    root -> right = build(pre_start + 1 + leftSize, pre_end, pos + 1, in_end);

    return root;
}


void makeEmpty(TreeNode *&root)
{
    if (root) {
        makeEmpty(root -> left);
        makeEmpty(root -> right);
        delete root;
        root = NULL;
    }
}

void calculateFreq(TreeNode *root)
{
    if (!root) return;
    if (!root -> left && !root -> right) {
        root -> freq = 1;
        return;
    }

    calculateFreq(root -> left); 
    calculateFreq(root -> right);
    root -> freq = (root -> left ? root -> left -> freq : 0) 
        + (root -> right ? root -> right -> freq : 0);
}

void preorderTraversal(TreeNode *root)
{
    if (!root) return;

    for (int i = 0; i < root -> freq; ++i) {
        cout << root -> ch;
    }
    cout << endl;
    preorderTraversal(root -> left);
    preorderTraversal(root -> right);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> preorder >> inorder;

    TreeNode *root = build(0, preorder.size(), 0, inorder.size());
    calculateFreq(root);

    preorderTraversal(root);

    makeEmpty(root);

    return 0;
}

一本通-1339：【例3-4】求后序遍历

#include <bits/stdc++.h>

using namespace std;

string preorder, inorder;

struct TreeNode
{
    char ch;
    TreeNode *left, *right;
    TreeNode(char x): ch(x), left(NULL), right(NULL) {}
};

TreeNode *treeBuild(int in_start, int in_end, int pre_start, int pre_end)
{
    if (in_start == in_end || pre_start == pre_end) return NULL;

    TreeNode *root = new TreeNode(preorder[pre_start]); //建立根节点

    int inRootPos = inorder.find(preorder[pre_start]);
    int leftSize = inRootPos - in_start;

    root -> left = treeBuild(in_start, inRootPos, pre_start + 1, pre_start + 1 + leftSize);
    root -> right = treeBuild(inRootPos + 1, in_end, pre_start + 1 + leftSize, pre_end);

    return root;
}

void postorderTraversal(TreeNode *root)
{
    if (!root) return;
    postorderTraversal(root -> left);
    postorderTraversal(root -> right);
    cout << root -> ch;
}

void makeEmpty(TreeNode *&root)
{
    if (root) {
        makeEmpty(root -> left);
        makeEmpty(root -> right);
        delete root;
        root = NULL;
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> preorder >> inorder;

    TreeNode *root = treeBuild(0, inorder.size(), 0, preorder.size());
    postorderTraversal(root);
    makeEmpty(root);

    return 0;
}

根据二叉树的中序和后序遍历结果构造二叉树¶

LeetCode 106.从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    using Iter = vector<int>::iterator;
    TreeNode* buildTreeFromInAndPost(Iter in_start, Iter in_end, Iter post_start, Iter post_end){
        if(in_start == in_end) return nullptr;
        if(post_start == post_end) return nullptr;

        auto root = new TreeNode(*(post_end - 1));
        auto inRootPos = find(in_start, in_end, *(post_end-1));
        auto rightSzie = distance(inRootPos+1, in_end);

        root -> right = buildTreeFromInAndPost(inRootPos+1, in_end, post_end-1-rightSzie, post_end-1);
        root -> left = buildTreeFromInAndPost(in_start, inRootPos, post_start, post_end - 1 - rightSzie);

        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeFromInAndPost(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }
};

根据二叉树的中序和层序遍历结果构造二叉树¶

一本通-1364：二叉树遍历(flist)

层序遍历的每一层的节点都是下一层的根节点，以测试用例为例：

首先根据层序遍历的第一个元素可知，A是根节点，然后在中序遍历里找到A，那么A的左边的元素就是左子树的元素，右边的元素是右子树的元素。这里我们判断左右两边是否存在元素，因为如果不存在元素的话，层序遍历的结果里是不会出现的。更确切的讲，比如A的右边无元素，那么意味着层序遍历的结果里第二层只有B一个元素。

用变量pos记录上一个根节点的位置，只需要从根节点往后开始寻找即可，比如到了B，位于左子树，只需要从DBE中查找，因为层序遍历是按照每一层元素出现的先后顺序显示的，那么最先匹配的就是先序遍历的根，所以直接输出即可。

#include <bits/stdc++.h>

using namespace std;

string inorder, levelorder;
int n;

void solve(int pos, int start, int end)
{
    bool flag = false;
    int j;
    for (int i = pos; i < n; ++i) {
        for (j = start; j <= end; ++j) {
            if (inorder[j] == levelorder[i]) {
                cout << levelorder[i];
                flag = true; break;
            }
        }
        if (flag) break;
    }

    if (start < j) solve(pos + 1, start, j - 1);
    if (j < end) solve(pos + 1, j + 1, end);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> inorder >> levelorder;
    n = inorder.size();
    solve(0, 0, n - 1);

    return 0;
}

扩展二叉树¶

一本通-1340：【例3-5】扩展二叉树

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

#include <bits/stdc++.h>

using namespace std;

class Tree
{
    struct TreeNode {
        char ch;
        TreeNode *left, *right;
        TreeNode(char x): ch(x), left(NULL), right(NULL) {}
    };
    TreeNode *root;
    int pos;

    void build(const string & s, TreeNode *& root)
    {
        if (s[++pos] != '.') {
            root = new TreeNode(s[pos]);
            build(s, root -> left);
            build(s, root -> right);
        }
        else root = NULL;
    }

    void inorderTraversal(TreeNode *root)
    {
        if (root) {
            inorderTraversal(root -> left);
            cout << root -> ch;
            inorderTraversal(root -> right);
        }
    }

    void postorderTraversal(TreeNode *root)
    {
        if (root) {
            postorderTraversal(root -> left);
            postorderTraversal(root -> right);
            cout << root -> ch;
        }
    }

    void makeEmpty(TreeNode *& root)
    {
        if (root) {
            makeEmpty(root -> left);
            makeEmpty(root -> right);
            delete root;
            root = NULL;
        }
    }

public:
    Tree(): root(NULL), pos(-1) {}

    ~Tree() { makeEmpty(root); }

    void build(const string & s){ build(s, root); }

    void inorderTraversal() { inorderTraversal(root); }

    void postorderTraversal() { postorderTraversal(root); }
};


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    cin >> s;
    Tree obj;
    obj.build(s);

    obj.inorderTraversal();
    cout << endl;
    obj.postorderTraversal();
    cout << endl;

    return 0;
}

一本通-1368：对称二叉树(tree_c)

核心是通过层序遍历结果构建二叉树，然后递归检查，也可以非递归的方法检查。但是也可以不建树的方法直接求得结果。

但是这道题还是可以练习如何通过扩展的层序遍历结果来构建二叉树（略微改编了题目）

与这道题相关联的是LeetCode 101.Symmetric Tree，注意题目背景区别还是很大的。

回到本题，我们可以发现其实给出的层序遍历恰好是一棵完全二叉树，那么我们就可以利用下标关系来进行检验了。相应的建树也变得很容易了。

//不建树，利用下标关系检查
#include <bits/stdc++.h>

using namespace std;

vector<char> s(1005);
int n = 0;

void solve()
{
    bool flag = true;

    for (int i = 1; i <= n; ++i) {
        int leftPos = 2 * i;
        int rightpos = leftPos + 1;
        if (leftPos > n && rightpos > n) break; //到了最后一层
        if (leftPos <= n && rightpos > n) { flag = false; break; }
        if ((s[leftPos] == '#' && s[rightpos] != '#') 
            || (s[leftPos] != '#' && s[rightpos] == '#')) {
            flag = false; break;
        }
    }

    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> s[++n]) {}
    --n;

    solve();

    return 0;
}

注意36行的--n，因为当最后一个空输入的时候，n的数值还是增加了。

那么我们来练习一下根据层序遍历的结果来建树。

//练习根据层序遍历结果建树
#include <bits/stdc++.h>

using namespace std;

vector<char> s(1005);
int n = 0;

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

TreeNode *build(int pos)
{
    if (pos > n || s[pos] == '#') return NULL;

    TreeNode *root = new TreeNode(s[pos]);
    root -> left = build(2 * pos);
    root -> right = build(2 * pos + 1);

    return root;
}

void makeEmpty(TreeNode *&root)
{
    if (root) {
        makeEmpty(root -> left);
        makeEmpty(root -> right);
        delete root;
        root = NULL;
    }
}

bool isSymmetric(TreeNode *root)
{
    if (!root) return true;
    if ((root -> left && !root -> right) 
        || (!root -> left && root -> right)) return false;

    return isSymmetric(root -> left) && isSymmetric(root -> right);
} 

void solve()
{
    TreeNode *root = build(1);
    bool flag = isSymmetric(root);
    makeEmpty(root);

    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> s[++n]) {}
    --n;
    solve();

    return 0;
}

LeetCode 297.二叉树的序列化与反序列化

这道题其实就是一本通-1340：【例3-5】扩展二叉树的一个翻版，只不过现在需要自己手动实现扩展二叉树的输出，并且有一个很重要的不同点，相比于一本通1340里的单个字母，二叉树里的节点存储的数值可能不止一位，所以需要用一个特殊的标记符号来对数据进行分隔。

序列化部分采用前序遍历的递归实现，注意需要去掉末尾的#符号，用pos记录处理到序列的哪个位置，然后递归构建左右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        string res;
        if (!root) return res;

        preorderTraversal(root, res);

        return res.substr(0, res.size() - 1);
    }

    void preorderTraversal(TreeNode *root, string & res)
    {
        if (!root) {
            res += ".#"; return;
        }

        res += to_string(root -> val);
        res.push_back('#');
        preorderTraversal(root -> left, res);
        preorderTraversal(root -> right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;

        int pos = 0;
        TreeNode *root;
        build(data, root, pos);
        return root;
    }

    void build(string & data, TreeNode *&root, int &pos)
    {
        int nextPos = data.find("#", pos);
        if (nextPos == string::npos) {
            string tmp = data.substr(pos);
            if (tmp.size() == 1 && tmp[0] == '.') root = NULL;
            else root = new TreeNode(stoi(tmp));
            return;
        }

        string tmp = data.substr(pos, nextPos - pos);
        pos = nextPos + 1;
        if (tmp[0] == '.') root = NULL;
        else {
            root = new TreeNode(stoi(tmp));
            build(data, root -> left, pos);
            build(data, root -> right, pos);
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

根据二叉树前序和后序遍历构造二叉树¶

之前结论已经指明，必须有中序遍历结果才能唯一确定一棵二叉树，现在回到它的逆问题，也就是给出前序和后序遍历结果，问能否构造出一棵这样的二叉树。

LeetCode 889.根据前序和后序遍历构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = pre.size();
        return build(0, n - 1, 0, n - 1, pre, post);
    }

    TreeNode *build(int pre_start, int pre_end, int post_start, int post_end, vector<int>& pre, vector<int>& post)
    {
        if (pre_start > pre_end || post_start > post_end) return NULL;

        TreeNode *root = new TreeNode(pre[pre_start]);
        TreeNode *l = NULL, *r = NULL;

        int pos = -1, leftSize = 0;
        if (pre_start < pre_end) {
            pos = find(post.begin(), post.end(), pre[pre_start + 1]) - post.begin();
            leftSize = pos - post_start + 1;
            l = build(pre_start + 1, pre_start + leftSize, post_start, post_start + leftSize - 1, pre, post);
        }

        if (pre_start + leftSize < pre_end) {
            r = build(pre_start + 1 + leftSize, pre_end, post_start + leftSize, post_end - 1, pre, post);
        }

        root -> left = l;
        root -> right = r;
        return root;
    }
};

以题目中的数据为例：

pre:  1 2 4 5 3 6 7
post: 4 5 2 6 7 3 1

根据前面利用中序和前序来构建二叉树的思路，我们希望得到如下结构
pre: [root][leftSize][rightSize]
post:[leftSize][rightSize][root]

于是思路是首先根据pre的第一个节点构建根节点，然后去判断leftSize是否不为0，如果不为0，那么就可以递归的去构建左子树。

在post里寻找leftSize的第一个元素，那么从post_start到这个元素之间就是左子树的元素
注意每次都要去检查leftSize和rightSize是否存在，不存在则节点为NULL

根据二叉树的前序遍历构造二叉搜索树¶

LeetCode 1008.先序遍历构造二叉树

二叉树没有限定子节点和根节点元素的大小关系，但是二叉搜索树因为限定了大小关系，所以仅仅给出其一个遍历结果，也能唯一确定的构造一个二叉树，只不过是二叉搜索树。

比如题目里的[8,5,1,7,10,12]，会发现10，12肯定在右子树，那么就很类似将链表转为二叉树的操作，找到第一个大于起始节点的值，然后递归的去实现，只需要注意一下边界条件即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = preorder.size();
        if (!n) return NULL;
        return build(preorder, 0, n - 1);
    }

    TreeNode *build(vector<int> & preorder, int start, int end)
    {
        TreeNode *root = new TreeNode(preorder[start]);
        int pos = start;
        while (pos <= end) {
            if (preorder[pos] > preorder[start]) break;
            else ++pos;
        }

        TreeNode *left = NULL, *right = NULL;
        if (pos - 1 - start > 0) left = build(preorder, start + 1, pos - 1);
        if (end - pos + 1 > 0) right = build(preorder, pos, end);
        root -> left = left;
        root -> right = right;

        return root;
    }
};