根据前序和中序遍历重建二叉树-摩杜云开发者社区

关于最近

最近在看算法相关的，接下来想记录一下自己学习的、个人认为比较值得记录的算法。
这篇博客主要是用自己的理解复述了根据中序、前序遍历重建二叉树这个博客的内容，大家可以主要看这个博客，我写得不如远矣。

根据前序和中序遍历重建二叉树

我们知道前序、中序、后序遍历二叉树有很多方法，比如递归进行遍历，使用栈/队列进行深度/广度优先遍历，更有甚者使用Morris方法进行额外空间复杂度为O(1)的遍历，但从遍历后的序列重建二叉树就比较麻烦。
这里描述一下从前序遍历序列和中序遍历序列重构二叉树的方法，要求二叉树没有重复的元素。
这里我先给出二叉树节点的定义：

struct TreeNode {
public:
    TreeNode(int val, TreeNode* left = nullptr, TreeNode* right = nullptr)
        : val(val), left(left), right(right)
    {}
    int val;
    TreeNode* left;
    TreeNode* right;
};

递归方法

数本身就是递归定义的，使用递归的方法来重构二叉树大概也是最简单的了吧。
我们先来看一棵树：
递归法举例的二叉树
其先序遍历为：4, 2, 1, 3, 6, 5
中序遍历为：1, 2, 3, 4, 5, 6
先序遍历的顺序为：根节点（当前节点）-左子树-右子树；
中序遍历的顺序为：左子树-根节点（当前节点）-右子树；
使用递归来重构一棵二叉树，其实就是递归地重构出某棵树的左右子树。那么如何递归的重构出左右子树呢？
递归一定要有终结的状态，而且要使得可变地参数逐步向终结状态靠近，否则递归就会无限的调用下去，直到栈爆掉。那么在重构过程中如何设置可变的参数，终结的状态又在哪里呢？
我们观察上面的先序遍历和中序遍历，可以发现在先序遍历中，一棵子树上的节点一定是靠在一起的比如4节点的左子树包括1, 2, 3，这三个节点在先序遍历和中序遍历都是靠在一起的，也就是说如果要重构出这棵子树只需要这个范围内的数字，范围不就变窄了吗，变量是不是就可以设置为先序遍历和后序遍历中该子树中元素的左侧下标和右侧下表，终结的状态是不是就可以设置为左右下标相等（意味着没有左右子树），或者左下标小于右下标（意味着越界，直接返回nullptr）？
我们继续往下看，如果这样设置参数如何来重构这棵树呢？我们来观察先序遍历，先序遍历的第一个节点必然是根节点，这样根节点就确定了，但我们还不知道左子树是哪些节点，右子树是哪些节点。因为我们要求二叉树中不能有重复节点，而我们又知道了当前的根节点，就可以在中序遍历中找到这个根节点。而中序遍历又是先遍历左子树，再遍历当前节点（根节点），再遍历右子树。那就简单了，从中序遍历的最左侧到根节点前面都是左子树的部分，从根节点右侧一直到中序遍历的最右侧都是右子树的部分，这样我们又可以得到左右子树各自的数量，就可以确定先序遍历中左右子树的范围了（先序遍历中从根节点到最右侧就分别是左子树和右子树）。
将上面的分析过程转化为代码如下：

class Solution {
public:
    TreeNode* rebuildTree(const std::vector<int>preOrder, const std::vector<int>& inOrder) {
        assert(preOrder.size() == inOrder.size());
        for (long idx = 0; idx < inOrder.size(); ++idx) { // 方便查找根节点在中序遍历中的下标
            inOrderIdx[inOrder[idx]] = idx;
        }
        return rebuildTree_aux(preOrder, inOrder, 0, preOrder.size()-1, 0, inOrder.size()-1);
    }
private:
    TreeNode* rebuildTree_aux(const std::vector<int>& preOrder, // 先序遍历序列
                            const std::vector<int>& inOrder,    // 中序遍历序列，其实用不到
                            long preLeftIdx, long preRightIdx,  // 重构当前子树用到的先序遍历的左右边界
                            long inLeftIdx, long inRightIdx) {  // 重构当前子树用到的中序遍历的左右边界
        assert(preRightIdx - preLeftIdx == inRightIdx - inLeftIdx);
        if(preLeftIdx > preRightIdx)    // 越界，直接返回nullptr
            return nullptr;
        TreeNode* root = new TreeNode(preOrder[preLeftIdx]);
        if(preLeftIdx == preRightIdx) // 只有一个节点，不评估左右子树
            return root;
        long inRootIdx = inOrderIdx[preOrder[preLeftIdx]]; // 查找根节点在中序遍历序列中的下标
        long leftSize = 0;  // 记录左子树的大小，用于在先序遍历序列中确定右子树的范围
        if(inRootIdx > inLeftIdx) {
            // 左边还有，左边有左子树
            long leftInLeftIdx = inLeftIdx;
            // 中序遍历，根节点左侧的节点就是左子树最右边的节点
            long leftInRightIdx = inRootIdx - 1;
            long leftDif = leftInRightIdx - leftInLeftIdx;
            leftSize = leftDif + 1;
            // 先序遍历，最左边节点（根节点）右边就是左子树的最左边节点
            long leftPreLeftIdx = preLeftIdx + 1;
            long leftPreRightIdx = leftPreLeftIdx + leftDif;
            root->left = rebuildTree_aux(preOrder, inOrder, leftPreLeftIdx, leftPreRightIdx, leftInLeftIdx, leftInRightIdx);
        }
        if (inRootIdx < inRightIdx) {
            // 中序遍历中，根节点右侧还有节点，是属于右子树的
            long rightInLeftIdx = inRootIdx + 1;
            long rightInRightIdx = inRightIdx;
            long rightDif = rightInRightIdx - rightInLeftIdx;
            long rightPreLeftIdx;
            // 下面可以合并，但为了清楚没有合并
            if (leftSize == 0) {
                // 如果没有左子树，那么先序遍历根节点后面的节点就是右子树的最左侧
                rightPreLeftIdx = preLeftIdx + 1;
            } else {
                // 如果有左子树，需要跳过左子树和根节点
                rightPreLeftIdx = preLeftIdx + 1 + leftSize;
            }
            long rightPreRightIdx = rightPreLeftIdx + rightDif;
            root->right = rebuildTree_aux(preOrder, inOrder, rightPreLeftIdx, rightPreRightIdx, rightInLeftIdx, rightInRightIdx);
        }
        return root;
    }
    std::unordered_map<long, long> inOrderIdx;
};

迭代方法

和上面一样，我们先来给出一棵树：
迭代法举例的二叉树
先序遍历：1, 2, 3, 4, 5, 6, 7, 8, 9
中序遍历：4, 3, 2, 5, 1, 7, 6, 8, 9
先序遍历的顺序为：根节点（当前节点）-左子树-右子树；
中序遍历的顺序为：左子树-根节点（当前节点）-右子树；

在先序遍历中，遍历某个子树时，总是从上到下先遍历该子树从根节点开始的左孩子。
什么时候到最左边呢？我们再看中序遍历，中序遍历在遍历一个子树的时候总是先遍历该子树的最左边节点，也就是说我们先当先序遍历到中序遍历该子树的中序遍历的第一个节点时，就到了最左侧节点。
后面就是该子节点或者其祖先节点右子树的部分了，那是哪个节点的右子树部分呢？我们在看中序遍历，如果一个节点的右子树是空的，那么其中序遍历的后一个节点就是其祖先节点。
也就是说我们在一开始组织遍历先序节点的时候建立一个栈，并有一个变量idx记录中序遍历的当前位置并初始化为0，每遍历一个节点就将其入栈stack，当遇到右孩子（即栈顶结点stack.top()等于inOrder[idx]）时，就将栈顶弹出并记录，向后移动中序遍历位置idx，查看栈顶结点和当前中序遍历的节点是否相等，相等就说明刚刚弹出的节点没有右孩子（因为其中序遍历的后一个节点是其父节点），继续弹出，直到不相等，就说明该节点是所弹出节点的右子树，设置恰当，将当前节点入栈，我们就可以遍历这个子树了。

将上述描述转化为代码如下：

class Solution1 {
public:
    TreeNode*
    rebuildTree(const std::vector<int>& preOrder, const std::vector<int>& inOrder) {
        long inIdx = 0;  // 用于遍历中序遍历序列
        long preSz = preOrder.size();
        std::stack<TreeNode*> parents;
        TreeNode* root = new TreeNode(preOrder[0]);
        parents.push(root);
        for (long preIdx = 1; preIdx < preSz; ++preIdx) {
            TreeNode* curNode = new TreeNode(preOrder[preIdx]);
            if (parents.top()->val != inOrder[inIdx]) {
                // 如果栈顶元素值和前序遍历的值不同，
                // 就说明还没有到左子树的最左边
                parents.top()->left = curNode;
                parents.push(curNode);
            } else {
                // 已经到了左子树的最左边
                // 查看栈中的下一个值和中序遍历的下一个值是否相等
                // 如果相等，则说明栈顶元素没有右孩子（因为中序遍历的下一个值是其父节点）
                // 则继续弹出节点，直至不相等
                TreeNode* poped;
                while (!parents.empty() // 被pop的是根节点
                        && parents.top()->val == inOrder[inIdx]) {
                    poped = parents.top();
                    parents.pop();
                    ++inIdx;
                }
                poped->right = curNode;
                parents.push(curNode);
            }
        }
        return root;
    }

};

验证

可以将恢复后的子树中序（或者先序）打印对比（或者保存对比），以验证我们确实恢复了二叉树。
下面提供Morris方法中序遍历一个二叉树并将其打印的代码：

void
MorrisInOrder(TreeNode* root) {
    TreeNode* cur = root;
    TreeNode* rightest;
    while (cur != nullptr) {
        if (cur->left) {
            rightest = cur->left;
            while(rightest->right && rightest->right != cur) {
                rightest = rightest->right;
            }
            if(rightest->right == nullptr) {
                rightest->right = cur;
                cur = cur->left;
                continue;
            } else { // rightest->right == cur;
                rightest->right = nullptr;
            }
        }
        std::cout << cur->val << ' ';
        cur = cur->right;
    }
    std::cout << '\n';
}