来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出前序遍历 preorder = [3,9,20,15,7],中序遍历 inorder = [9,3,15,20,7],返回如下的二叉树:
1 2 3 4 5 |
3 / \ 9 20 / \ 15 7 |
二、题解
这道题在《剑指offer》也出现了,题目完全一样。主要用到了树的两个特性:
- 前序遍历的首元素为根节点。
- 中序遍历中,根节点的左边是左子树,根节点的右边是右子树。
解题的思路就是:通过前序遍历得到根节点,然后在中序遍历中找到这个节点,再通过递归的方式找出左右子树。
详细的分析可以参考《剑指offer》面试题7:重建二叉树。
三、代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/** * 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 { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { size_t len = preorder.size(); if (len < 1) return nullptr; return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1); } private: TreeNode *buildTreeCore(vector<int> &preOrder, unsigned int preStart, unsigned int preEnd, vector<int> &inOrder, unsigned int inStart, unsigned int inEnd) { unsigned int idx, lchild_len; TreeNode *root = nullptr; root = new TreeNode(preOrder[preStart]); if (preStart == preEnd) { return root; } // 在中序遍历中找到根节点 idx = inStart; while (idx < inEnd && root->val != inOrder[idx]) { idx++; } // 左子树的长度 lchild_len = idx - inStart; if (lchild_len > 0) { // 计算左子树 root->left = buildTreeCore(preOrder, preStart + 1, preStart + lchild_len, inOrder, inStart, idx - 1); } if (lchild_len < preEnd - preStart) { // 计算右子树 root->right = buildTreeCore(preOrder, preStart + lchild_len + 1, preEnd, inOrder, idx + 1, inEnd); } return root; } }; |
执行通过:
评论