一、題目大意
給定兩個整數陣列，preorder 和 postorder ，其中 preorder 是一個具有 無重復 值的二叉樹的前序遍歷，postorder 是同一棵樹的后序遍歷，重構并回傳二叉樹，
如果存在多個答案，您可以回傳其中 任何 一個，
示例 1：
輸入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
輸出：[1,2,3,4,5,6,7]
示例 2:
輸入: preorder = [1], postorder = [1]
輸出: [1]
提示：
- 1 <= preorder.length <= 30
- 1 <= preorder[i] <= preorder.length
- preorder 中所有值都 不同
- postorder.length == preorder.length
- 1 <= postorder[i] <= postorder.length
- postorder 中所有值都 不同
- 保證 preorder 和 postorder 是同一棵二叉樹的前序遍歷和后序遍歷
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
先序遍歷順序是根左右，后序遍歷順序是 左右根，要建立樹，肯定要從根節點開始創建，然后再創建左右子節點，根據先序和后序的特點，根節點的位置是固定的，即是先序遍歷的第一個，又是后序遍歷的最后一個，知道了根節點位置，我們需要分隔左右子樹的區間，
先序遍歷：[1][2,4,5][3,6,7]
后序遍歷：[4,5,2][6,7,3][1]
先序和后序中各自左子樹區間長度相等，數字順序可能不同，通過觀察2和3分別是左子樹和右子樹的根節點（先序的頭后序的尾），可以根據其來定位左右子樹區間的位置范圍了，拆分陣列，可以用雙指標來指向子區間的開頭和末尾，用preL和preR分別代表左子樹區間的開頭和結尾位置，postL和postR表示右子樹區間的開頭和結尾位置，那么若preL大于preR或者postL大于postR的時候，說明已經不存在子樹區間，直接回傳空指標，然后要先新建當前樹的根節點，就通過pre[preL]取到即可，接下來要找左子樹的根節點在post中的益，最簡單的方法就是遍歷post中的區間[postL, postR]，找到其位置idx，然后根據這個idx就可以算出左子樹區間長度為len = (idx - postL) + 1，那么pre陣列中左子樹區間為[preL+1, preL+len]，右子樹區間為[preL+1+len, preR]，同理，post陣列中左子樹區間為[postL, idx]，右子樹區間為[idx+1, postR-1]，知道了這些資訊，就可以呼叫遞回函式了，
三、解題方法
3.1 Java實作
public class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
return helper(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
}
TreeNode helper(int[] pre, int preL, int preR, int[] post, int postL, int postR) {
if (preL > preR || postL > postR) {
return null;
}
TreeNode node = new TreeNode(pre[preL]);
if (preL == preR) {
return node;
}
int idx = -1;
for (idx = postL; idx <= postR; idx++) {
if (pre[preL + 1] == post[idx]) {
break;
}
}
node.left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
node.right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
return node;
}
}
四、總結小記
- 2022/10/6 今天今天有點冷
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510967.html
標籤：其他
上一篇：原始遞回函式及模擬運行的優化