《剑指offer》 07.重建二叉树

剑指offer
留言

note: 知道任何两种遍历的方式，来重建二叉树是非常经典的数据结构题目。思路非常的简单，实现起来却没有思考时写写画画那么简单。其中重点我觉得是一种将子树看为全新的树的思想。

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

限制：

0 <= 节点个数 <= 5000

方法一 递归

思路

一般而言针对二叉树最直白最好写的方法就是递归。

当然首先我们需要明确前序遍历和中序遍历的顺序

前序遍历：

  • 先遍历根节点
  • 然后遍历左子树
  • 然后遍历右子树

中序遍历：

  • 先遍历左子树
  • 然后遍历根节点
  • 然后遍历右子树

如果我们有子节点就是一棵树的概念的话，我们很容易发现，对于每棵树，前序遍历中序遍历的形式都是不变的，即：

1
2
[root,[左子树],[右子树]]	//	前序遍历
[[左子树],root,[右子树]]	// 中序遍历

方括号括着的部分，显然就是我们递归的函数了。这样问题就转换成了如何准确的找到要递归的部分，也就是两个遍历顺序中的，方括号的位置的问题，以及root所在位置的问题。

那我们可以考虑我们的递归函数的传参

  • 首先肯定要有前序遍历和中序遍历的数组，
  • 然后我们需要明确定位要递归的那部分，本来我们可能需要8个参数来确定所有的方括号，但是我们很容易发现，前序遍历左子树的右括号和右子树的左括号有关系，中序遍历的左子树右括号和右子树的左括号也有关系，所以我们的括号只需要4个参数就可以确定。
  • 然后可能会有疑问，root不需要定位么？事实上前序遍历确实不需要遍历，每个方括号内第一个元素肯定是root，但是对于中序遍历就需要定位了。这时候一般有两种解决方案，一种是遍历找，显然很复杂，另一种是我们在开始前就用一个hash表，记录下来前序遍历中每一个元素对应在中序遍历的位置，这样就可以很快的在中序遍历中对root进行定位。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 {
    unordered_map<int,int> dic;

public:
    TreeNode* buildMyTree(vector<int>& preorder,vector<int>& inorder,int p_left,int p_right,int i_left,int i_right){
        if(p_left>p_right)
            return NULL;
        int p_root = p_left;
        int i_root = dic[preorder[p_root]];

        int size = i_root-i_left;

        TreeNode* node = new TreeNode(preorder[p_root]);

        node->left = buildMyTree(preorder,inorder,p_left+1,p_left+size,i_left,i_root-1);
        node->right = buildMyTree(preorder,inorder,p_left+size+1,p_right,i_root+1,i_right);
        return node;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size();
        for(int i=0;i<n;i++){
            dic[inorder[i]] = i;
        }

        return buildMyTree(preorder,inorder,0,n-1,0,n-1);
    }
};

复杂度

  • 时间复杂度$O(n)$。n是树的节点数目。我们在定位时没有使用遍历等复杂的手段，如果我们定位中序遍历的root没有使用hash的话，可能就要$O(n^2)$的复杂度了
  • 空间复杂度$O(n)$。首先我们使用了hash映射，额外使用了$O(n)$的空间来存储每个结点的位置，当然递归本身也有$O(h)$的栈开销，但是显然$h<n$。所以额外使用的空间为$O(n)$

方法二 迭代

思路

二叉树的迭代法一直我看来要比递归难写，这道题尤其是这样子。

这道题的迭代写法主要是利用了前序遍历和中序遍历结果的部分一致性，以及他们的部分相反性。主要考察的还是对前序遍历 中序遍历的了解熟悉程度。

整理知识点我觉得可以有以下几个重点

  • 前序遍历的相邻节点的关系。前序遍历中任何相邻的两个节点，隐藏着一个关系：后一个节点要么是前一个节点的左子树，要么就是前一个节点的某个祖先节点的右子树（此时说明前一个节点没有左子树）。这其实是一个很好理解的性质，一会儿会有所帮助
  • 中序遍历最前面的节点。表示的时当前的二叉树最左边（指的是从不选择右子树）的节点。这个也很好理解。
  • 我们使用栈这种数据结构，维护在前序遍历中还没有考虑右子树情况的节点。为什么要用栈呢？因为有这样一个性质，在剔除掉二叉树中的任何一个右子树后，前序遍历的顺序和中序遍历的顺序必然是相反的。这样利用先进后出的的栈的性质，我们就可以将前序遍历和中序遍历进行对应。
  • 前三点都有一个共性，那就是我们想方设法不考虑右子树的存在。但是右子树终究避免不了，那么右子树在哪里呢？就是在我们在第三点中剔除掉的位置。只要能找到这些位置，我们就可以将右子树的节点找到，并根据它和栈中元素的关系，接到右分支上。
  • 那么右子树节点对应栈中哪个元素呢？当我们利用出栈操作来和中序遍历进行对应时，一但栈顶元素和中序遍历第index个元素不对应了，那么就说明index个元素是一个右子树节点，而且必然是上一个弹出的节点是它的父节点——只有这个原因，才会导致栈顶元素不再是中序遍历中index个元素。

实现步骤分为以下几步

  • 建立存放节点的栈，将前序遍历的第一个元素放进去（因为这个必定是树的根节点）
  • 建立index变量，指向中序遍历的第一个元素，作为“当前树最左节点”
  • 遍历前序遍历元素，每个元素先建立为一个节点，根据当前栈顶元素是否和index所指元素相等，来执行不同的操作
    • 如果当前栈顶节点的值和index所指元素相同，说明还没有碰到右子树，那么当前前序遍历的元素，即为栈顶节点的左子树。栈顶节点左子树指针指向新节点
    • 如果当前栈顶节点的值和index所指元素不同，说明碰到了右子树，那么当前前序遍历的元素，应该是栈中某个节点的右子树。那么移动index并不断出栈节点，并记录下来刚刚出栈的节点，直到index所指向的元素不等于栈顶节点的值，那么前一个出栈的节点就是该元素的父节点，该元素所生成的节点就是出栈节点的右子树，出栈节点右子树指针指向新节点。如果移动中栈空了，那就停止移动index。进行下一步操作
  • 将新节点进行入栈，因为新节点我们并没有考虑它自身的左右子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n==0)
            return NULL;
            
        stack<TreeNode*> stk;
        TreeNode* root = new TreeNode(preorder[0]);
        int index=0;
        stk.push(root);

        for(int i=1;i<n;i++){
            TreeNode* curnode = new TreeNode(preorder[i]);
            if(inorder[index] != stk.top()->val){
                stk.top() -> left = curnode;
            }else{
                TreeNode* pnode;
                while(!stk.empty() && inorder[index]==stk.top()->val){
                    pnode = stk.top();
                    stk.pop();
                    index++;
                }
                pnode->right = curnode;
            }
            stk.push(curnode);
        }

        return root;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。同样我们只是遍历了所有的树的节点一次。
  • 空间复杂度$O(n)$。虽然尽管我们没有使用递归空间，但是我们使用了栈空间来保存树，所以依然还是线性复杂。