欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

程序员文章站 2022-06-18 17:54:00
...

LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

题目大意: 根据一个二叉树的先序遍历序列和中序遍历序列,构造出该二叉树。

解题思路

根据给定的先序遍历序列,可以知道根的值,然后根据该值在中序遍历中划分左右子树,直到子树为空。如给定的例子:
1. 根据先序序列,可知,根节点的值为 3。
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
2. 在中序序列中找到该值,就可以划分出左子树和右子树。
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
划分的子树:
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
3. 同理, 对左子树做同样的操作:
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
4. 对右子树做同样的操作:
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

AC 代码

/**
 * 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 
{
private:
    // 根据先序遍历序列的 [preBeg, preBeg+size) 和 中序遍历的 [inBeg, inBeg+size) 构建二叉树的子树
    TreeNode* buildTree(vector<int>& preorder, int preBeg, 
                              vector<int>& inorder, int inBeg, int size)
    {
        if(size <= 0) return nullptr;

        TreeNode* curNode = new TreeNode(preorder[preBeg]);

        int inorderLeftTreeEnd = inBeg;
        while(inorder[inorderLeftTreeEnd] != preorder[preBeg]) ++inorderLeftTreeEnd;
        int leftTreeSize = inorderLeftTreeEnd - inBeg;
        int rightTreeSize = (inBeg + size) - inorderLeftTreeEnd - 1;

        curNode->left = buildTree(preorder, preBeg+1, inorder, inBeg, leftTreeSize);
        curNode->right = buildTree(preorder, preBeg+1+leftTreeSize, 
                                         inorder, inorderLeftTreeEnd+1, rightTreeSize);

        return curNode;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        return buildTree(preorder, 0, inorder, 0, preorder.size());
    }
};