溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何重建python二叉樹，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
前序遍歷的第一個值為根節點的值，使用這個值將中序遍歷結果分成兩部分，左部分為樹的左子樹中序遍歷結果，右部分為樹的右子樹中序遍歷的結果，遞歸地去分別構建它的左右子樹。
package Tree;import java.util.HashMap;/*** 重建二叉樹* 輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。*/public class Solution54 {private HashMap<Integer, Integer> inOrderNumsIdx = new HashMap<>(); // 緩存中序遍歷數組的每個值對應的索引public TreeNode reConstructBinaryTree(int[] pre, int[] in) {for (int i = 0; i < in.length; i++) {inOrderNumsIdx.put(in[i], i);}return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);}private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {if (preL == preR) return new TreeNode(pre[preL]);if (preL > preR || inL > inR) return null;// 創建當前根節點，并為根節點賦值TreeNode root = new TreeNode(pre[preL]);int inIdx = inOrderNumsIdx.get(root.val);int leftTreeSize = inIdx - inL;// 構建左子樹root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, in, inL, inL + leftTreeSize - 1);// 構建右子樹root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, in, inL + leftTreeSize + 1, inR);return root;}public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}}
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
