重建二叉树 - 遍历二叉树的三种方式

一时失言乱红尘 2022-12-16 09:27 206阅读 0赞

## 重建二叉树 ##

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

**示例**：

前序遍历 preorder = \[3,9,20,15,7\]  
中序遍历 inorder = \[9,3,15,20,7\]  
返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

**限制**：

0 <= 节点个数 <= 5000

--------------------

## 二叉树的三种遍历方式 ##

*  前序遍历，又称为先根遍历(DLR)
 *  中序遍历(LDR)
 *  **后续遍历(LRD)(本题没有用到)**  
    先序遍历序列`[pre_start:pre_end]`  
    中序遍历序列区间`[ino_start;ino_end]`

这个题的解法是根据先序遍历和中序遍历的规律，在先序遍历的序列中，因为第一个节点一定是根节点`cur_root`，所以在中序遍历中寻找这个根节点的位置`pos`，然后以`pos`为中点，把中序遍历的序列分为两部分：左子树`[ino_start:pos-1]`、右子树`[pos+1:ino_end]`(相当于把一棵树的根砍掉，分成了两棵树)，然后根据pos在原来先序遍历的系列中，也把先序遍历的序列分为两部分：左子树`[start+1:pos]`、右子树`[pos:end]`。由此把一个大问题分成了两个子问题，分别在左子树和右子树重复该操作。

## 解法 ##

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){ 
        // 明白DLR LVR的意义所在。
        // 先序遍历的第一个节点是根节点
        struct TreeNode *node = malloc(sizeof(struct TreeNode));
        // 记录根节点在中序遍历中的位置
        int pos;
        int pre_num = 0;
        // 如果树节点是0个，返回NULL
        if(preorderSize == 0) return NULL;
        while(pre_num < preorderSize){ 
            if(inorder[pre_num] == *preorder){ 
                pos = pre_num;
                break;
            }
            pre_num++;
        }
        node->val = *preorder;
        node->left = buildTree(preorder+1,pre_num,inorder,pre_num);
        node->right = buildTree(preorder+pos+1,preorderSize-pre_num-1,inorder+pos+1,preorderSize-pre_num-1);
        return node;
    }