一、題目大意
給定兩個整數陣列 inorder 和 postorder ，其中 inorder 是二叉樹的中序遍歷， postorder 是同一棵樹的后序遍歷，請你構造并回傳這顆 二叉樹 ，
示例 1:
輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]
示例 2:
輸入：inorder = [-1], postorder = [-1]
輸出：[-1]
提示:
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder 和 postorder 都由 不同 的值組成
- postorder 中每一個值都在 inorder 中
- inorder 保證是樹的中序遍歷
- postorder 保證是樹的后序遍歷
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
要求從中序和后序遍歷的結果來重新建原二叉樹，中序遍歷順序是左 根 右，后序遍歷順序是左 右 根，對于這種樹的重建一般采用遞回來做，由于后序的順序的最后一個肯定是根，所以原二叉樹的根節點可以知道，題目中給了一個很關鍵的條件就是樹中沒有相同元素，有了這個條件就可以在中序遍歷中也定位出根節點的位置，并根據根節點的位置將中序遍歷拆分為春熙路右兩部分，分別對其遞回呼叫原函式，
三、解題方法
3.1 Java實作
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
TreeNode helper(int[] in, int inL, int inR, int[] post, int postL, int postR) {
if (inL > inR || postL > postR) {
return null;
}
TreeNode node = new TreeNode(post[postR]);
int i = 0;
for (i = inL; i < in.length; i++) {
if (in[i] == node.val) {
break;
}
}
node.left = helper(in, inL, i - 1, post, postL, postL + i - inL - 1);
node.right = helper(in, i + 1, inR, post, postL + i - inL, postR - 1);
return node;
}
}
四、總結小記
- 2022/10/7 明天又是新的一天
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511000.html
標籤：其他
上一篇：linux引導和服務