本文共 2505 字,大约阅读时间需要 8 分钟。
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:3 / \ 9 20 / \ 15 7
来源:力扣(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]此时根据inorder的左子树序列可以确定,将preorder分为左子树序列 [9] 和右子树序列 [20,15,7];
conquer
构造根节点root(3),然后递归地处理左子树序列和右子树序列,分别作为左子树left和右子树right。combine
将二叉树拼接起来,即root->left = left,root->right = right, 返回root。/** * 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 { vector preorder; vector inorder;public: TreeNode* buildTree(vector & preorder, vector & inorder) { this->preorder = preorder; this->inorder = inorder; return dfs(0, preorder.size()-1, 0, inorder.size()-1); } TreeNode* dfs(int startPre, int endPre, int startIn, int endIn) { if (startPre > endPre or startIn > endIn) { return NULL; } if (startPre == endPre or startIn == endIn) { return new TreeNode(preorder[startPre]); } TreeNode * root = new TreeNode(preorder[startPre]); int rootPos = findRootPosInorder(preorder[startPre], startIn, endIn); if (rootPos < 0) { return NULL; } int leftStartIn = startIn; int leftEndIn = rootPos-1; int rightStartIn = rootPos+1; int rightEndIn = endIn; int leftSize = rootPos-startIn; int leftStartPre = startPre+1; int leftEndPre = startPre+leftSize; int rightStartPre = startPre + leftSize + 1; int rightEndPre = endPre; root->left = dfs(leftStartPre, leftEndPre, leftStartIn, leftEndIn); root->right = dfs(rightStartPre, rightEndPre, rightStartIn, rightEndIn); return root; } int findRootPosInorder(int value, int startIn, int endIn) { for (int i = startIn; i <= endIn; i++) { if (value == inorder[i]) { return i; } } return -1; }};