剑指offer 重建二叉树

问题描述

面试题07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出

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

返回如下的二叉树：

问题分析

首先明确二叉树的前序遍历和中序遍历的定义。

前序遍历：先访问根结点，再访问根结点的左子树，最后访问根结点的右子树；
中序遍历：先访问根结点的左子树，再访问根结点，最后访问根结点的右子树。

可以自己试一试写出上面的二叉树的前序和中序，这样做有助于接下来的理解。
根据定义可以总结出一些性质：

前序遍历的性质：访问的第一个节点必然是根结点，即3一定是根结点；
中序遍历的性质：根结点分隔左右子树，即通过先序已经知道了根结点是3，则[9]一定是3的左子树，[15,20,7]一定是3的右子树。

根据以上两条性质，就可以确定一个节点以及它的左右子树。
问题解决的步骤：
（1）根据当前子树（子树也是二叉树）的前序遍历的第一个节点确定当前子树的根结点；
（2）根据当前子树（子树也是二叉树）的中序遍历确定根结点的左右子树；
（3）对左右子树再分别执行步骤（1）和（2）；
（4）如果只剩余一个节点，那么这就是叶结点。无需再进行划分。

代码实现

#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

typedef struct TreeNode TNode;

// create a new node
TNode *newTreeNode(int val) {
  TNode *tnode = (TNode *)malloc(sizeof(TNode));
  tnode->val = val;
  return tnode;
}

TNode *rebuild(int *preorder, int pl, int pr, int *inorder, int inl, int inr) {
  if(pl > pr) return NULL;
  TNode *tnode = newTreeNode(preorder[pl]);
  if (pl <= pr) {
    int mid = inl;
    for (; mid <= inr; mid++) {
      if (inorder[mid] == preorder[pl]) {
        break;
      }
    }
    // 左子树节点的数量
    int leftTreeSize = mid - inl;
    tnode->left = rebuild(preorder, pl+1, pl + leftTreeSize, inorder, inl, mid-1);
    tnode->right = rebuild(preorder, pl+leftTreeSize+1, pr, inorder, mid+1, inr);
  }

  return tnode;
}

struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
  return rebuild(preorder, 0, preorderSize-1, inorder, 0, inorderSize-1);
}

// 先序遍历 测试一下
void preOrderTest(TNode *root) {
  printf("%d  ", root->val);
  if(root->left != NULL) preOrderTest(root->left);
  if(root->right != NULL) preOrderTest(root->right);
}

int main() {
  int preorder[] = {3,9,20,15,7};
  int inorder[] = {9,3,15,20,7};
  TNode* treeRoot = buildTree(preorder, 5, inorder, 5);
  preOrderTest(treeRoot);
  return 0;
}

特殊情况

（1）二叉树为空
（2）二叉树存在重复元素。

第（1）个情况很好解决，但是第二个就要考虑一下了。比如下面这种情况：

（0）既有左孩子又有右孩子
  3
 / 
3   3

前序序列：[3,3,3]
中序序列：[3,3,3]

根据前序和中序能否还原二叉树呢？看下面这两棵树：

(1)只有左孩子
    3
   /
  3
 /
3

(2)只有右孩子
3
 
  3
   
    3

因为上图这（0）（1）（2）三棵树的前序和后序相同，所以不能确定唯一的二叉树。
是否包含重复元素的所有二叉树都无法被还原呢？考虑下面这种情况：

（4）包含相同元素的二叉树
  3
 / 
2   3
前序序列：[3,2,3]
中序序列：[2,3,3]

似乎这种情况是可以唯一确定二叉树的。也就是说在有重复元素的情况下，有可能是可以唯一确定二叉树的。幸好这个题目指明了没有重复元素，否则代码需要做一些调整。

测试

直接输出重建的二叉树的前序和中序，与原本的序列对照即可。

// 先序遍历 测试一下
void preOrderTest(TNode *root) {
  printf("%d  ", root->val);
  if(root->left != NULL) preOrderTest(root->left);
  if(root->right != NULL) preOrderTest(root->right);
}

如有不当之处，欢迎指出！