劍指 Offer 07. 重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。

例如，給出

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

返回如下的二叉樹：

3/ \9 20/ \15 7

限制：

0 <= 節點個數 <= 5000

算法：

遞歸

C++代碼

/*** 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> index; public:TreeNode* Rebuildtree(vector<int>& preorder, vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){if(preorder_left > preorder_right)return NULL;//前序遍歷的第一個節點就是根節點(preorder_left)int preorder_root = preorder_left;//根節點在中序遍歷出現的位置int inorder_root = index[preorder[preorder_root]];//創建根節點TreeNode* root = new TreeNode(preorder[preorder_root]);//得到左子樹中的節點數目int size_left_subtree = inorder_root - inorder_left;//遞歸構造左子樹 并連接到根節點//前序遍歷的「從 左邊界+1 開始的 size_left_subtree」個元素就對應了中序遍歷中「從 左邊界 開始到 根節點定位-1」的元素root->left = Rebuildtree(preorder, inorder, preorder_left+1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);root->right = Rebuildtree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int len = preorder.size();//構建哈希表 方便后續直接在中序遍歷中找到根節點的位置for(int i = 0; i < len; i++){index[inorder[i]] = i;} //提供前序遍歷和中序遍歷的值及其范圍return Rebuildtree(preorder, inorder, 0, len - 1, 0, len - 1);} };

?

總結

以上是生活随笔為你收集整理的根据二叉树前序遍历和中序遍历重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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