本文共 2536 字,大约阅读时间需要 8 分钟。
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:3 / \ 9 20 / \ 15 7
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
后序遍历序列的最后一个元素即为根节点。
中序遍历序列的根节点位于中间,左边为其左子树构成的中序遍历序列,右边为其右子树构成的中序遍历序列。
根据左右子树的序列长度,就可以确定后序遍历序列的左右子树序列的分界点。
举例来说明分治法思想的运用。
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]此时根据inorder的左子树序列可以确定,将postorder分为左子树序列 [9] 和右子树序列 [15,7,20];
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 inorder; vector postorder;public: TreeNode* buildTree(vector & inorder, vector & postorder) { this->inorder = inorder; this->postorder = postorder; return dfs(0, inorder.size()-1, 0, postorder.size()-1); } TreeNode* dfs(int startIn, int endIn, int startPost, int endPost) { if (startPost > endPost or startIn > endIn) { return NULL; } if (startPost == endPost or startIn == endIn) { return new TreeNode(postorder[startPost]); } TreeNode * root = new TreeNode(postorder[endPost]); int rootPos = findRootPosInorder(postorder[endPost], 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 leftStartPost = startPost; int leftEndPost = startPost + leftSize-1; int rightStartPost = startPost + leftSize; int rightEndPost = endPost-1; root->left = dfs(leftStartIn, leftEndIn, leftStartPost, leftEndPost); root->right = dfs(rightStartIn, rightEndIn, rightStartPost, rightEndPost); 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; }};