文章目錄

• 題目描述
• 代碼 & 思路

題目描述

• 這題主要是考察前序、后序的性質(zhì)，以及相互間的關(guān)系
  

代碼 & 思路

• 前序：根 - 左 - 右； 中序：左 - 根 - 右，那么用前序數(shù)組的首位（即根）的值到中序數(shù)組查找對(duì)應(yīng)位置，就可以由此得到左右子樹的結(jié)點(diǎn)數(shù)。
• 遞歸進(jìn)行，每次構(gòu)造當(dāng)前根結(jié)點(diǎn)，然后開啟左、右子樹的遞歸函數(shù)即可。
• 用一次循環(huán)來構(gòu)建<根結(jié)點(diǎn)val，中序index>的哈希表，就不用每次都循環(huán)查找一次根節(jié)點(diǎn)index。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/ class Solution {/**如何遞歸？題目要求：給定前序和后序，構(gòu)造樹。既然是前序和后序，那么數(shù)組中左子樹和右子樹一定可以分離成兩個(gè)連續(xù)子數(shù)組沖！*/public TreeNode buildTree(int[] preorder, int[] inorder) {// 根據(jù)preorder中的一個(gè)值，就能找到在inorder中的位置Map<Integer,Integer> map = new HashMap();for(int i=0;i < inorder.length;i++){map.put(inorder[i],i);}return toBuildTree(new TreeNode(),preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);}TreeNode toBuildTree(TreeNode root, int[] preorder, int pL, int pR, int[] inorder, int iL, int iR, Map<Integer,Integer> map){// 找到root.val在inorder中的位置int rootIndex = map.get(preorder[pL]);root = new TreeNode(inorder[rootIndex]);// 左右子樹結(jié)點(diǎn)數(shù)量int leftNum = rootIndex - iL;int rightNum = iR - rootIndex;// 左右子樹構(gòu)建if(leftNum > 0){root.left = toBuildTree(root.left, preorder, pL + 1, pL + leftNum, inorder, iL, rootIndex - 1, map);}if(rightNum > 0){root.right = toBuildTree(root.right, preorder, pL + leftNum + 1, pR, inorder, rootIndex + 1, iR, map);}return root;} }

• 無注釋版

class Solution {Map<Integer, Integer> hashmap = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i = 0; i < inorder.length; i++) {hashmap.put(inorder[i], i);}return toBuildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}public TreeNode toBuildTree(int[] preorder, int pL, int pR, int[] inorder, int iL, int iR) {int rootIndex = hashmap.get(preorder[pL]);TreeNode root = new TreeNode(preorder[pL]);int leftNum = rootIndex - iL;int rightNum = iR - rootIndex;if(leftNum > 0) {root.left = toBuildTree(preorder, pL + 1, pL + leftNum, inorder, iL, rootIndex - 1);}if(rightNum > 0) {root.right = toBuildTree(preorder, pL + leftNum + 1, pR, inorder, rootIndex + 1, iR);}return root;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】105. 从前序与中序遍历序列构造二叉树（Java、递归、二叉树、哈希表）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。