17(105) 從前序與中序遍歷序列構造二叉樹(Medium)

描述

根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

示例

例如，給出前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7]返回如下的二叉樹：3/ 9 20/ 15 7

Description

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

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

Example

For example, givenpreorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree:3/ 9 20/ 15 7

BitDance Amazon Microsoft Adobe Apple Google Tencent Mi HuaWei VMware

解題

遞歸解法

class Solution { public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()) return NULL;TreeNode* root=new TreeNode(preorder[0]);vector<int> preorder_left, inorder_left, preorder_right, inorder_right;int i;for(i=0;i<inorder.size();++i){if(inorder[i]==root->val) break;inorder_left.push_back(inorder[i]);}//中序遍歷根結點的左子樹存入inorder_leftfor(++i;i<inorder.size();++i){inorder_right.push_back(inorder[i]);}//中序遍歷根結點的右子樹存入inorder_rightfor(int j=1;j<preorder.size();++j){//根據中序遍歷左子樹的長度來確定前序遍歷左子樹存入preorder_leftif(j<=inorder_left.size()) preorder_left.push_back(preorder[j]);//前序遍歷剩下的為右子樹 存入前序遍歷右子樹序列preorder_rightelse preorder_right.push_back(preorder[j]);}root->left=buildTree(preorder_left,inorder_left);root->right=buildTree(preorder_right,inorder_right);return root;} };

總結

以上是生活随笔為你收集整理的二叉树 中序遍历 python_LeetCode 105 树 从前序与中序遍历序列构造二叉树(Medium)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。