難度：中等
頻次：68

題目:

給定兩個整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節(jié)點。

解題思路：遞歸

注意：

• **規(guī)律：**先序遍歷的根節(jié)點在最前面，中序遍歷的根節(jié)點在相對中間的地方
• 所以只要每次都找到根節(jié)點，然后去掉根節(jié)點，把兩個先序數(shù)組和中序數(shù)組都分別拆成2個數(shù)組
• 然后用左邊的兩個數(shù)組對root.left使用遞歸就行，右邊同理
• Arrays.copyOfRange(List,a,b)
  • 這個函數(shù)需要注意，函數(shù)命需要記住，一個s，然后O、R大寫
  • 范圍是[a,b)===》即不包括b

代碼

/*** 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 {public TreeNode buildTree(int[] preorder, int[] inorder) {//如果數(shù)組都為null，則說明樹為空===>遞歸結束條件//【可以理解到空節(jié)點說明這條遞歸路徑結束】if(preorder.length==0&&inorder.length==0) return null;//先保存根節(jié)點===》每次遞歸真正有用的就是保存這個節(jié)點，剩下的都是遞歸TreeNode root=new TreeNode(preorder[0]);for(int i=0;i<inorder.length;i++){if(preorder[0]==inorder[i]){//前序遍歷，root根節(jié)點在最前面，把這個去掉，所以是從1開始int[] pre1=Arrays.copyOfRange(preorder,1,i+1);int[] pre2=Arrays.copyOfRange(preorder,i+1,preorder.length);//中序遍歷，root根節(jié)點在最中間，所以要把遍歷到的這個i去掉，所以是到i[函數(shù)不包含到i]int[] in1=Arrays.copyOfRange(inorder,0,i);int[] in2=Arrays.copyOfRange(inorder,i+1,inorder.length);root.left=buildTree(pre1,in1);root.right=buildTree(pre2,in2);break;}}return root;} }

總結

以上是生活随笔為你收集整理的leetcode 105. 从前序与中序遍历序列构造二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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