如何重建python二叉樹，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
十多年的文登網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整文登建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“文登網(wǎng)站設計”,“文登網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
思路
前序遍歷的第一個值為根節(jié)點的值，使用這個值將中序遍歷結(jié)果分成兩部分，左部分為樹的左子樹中序遍歷結(jié)果，右部分為樹的右子樹中序遍歷的結(jié)果，遞歸地去分別構建它的左右子樹。
代碼實現(xiàn)
package Tree;
import java.util.HashMap;
/** * 重建二叉樹 * 輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。 */public class Solution54 { private HashMap inOrderNumsIdx = new HashMap<>(); // 緩存中序遍歷數(shù)組的每個值對應的索引
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; // 創(chuàng)建當前根節(jié)點，并為根節(jié)點賦值 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; } }}
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。
網(wǎng)站名稱：如何重建python二叉樹
標題鏈接：
http://weahome.cn/article/jsojde.html
重慶分公司
重慶分公司
