每天一道leetcode-105從前序和中序序列構建二叉樹
- 2019 年 10 月 4 日
- 筆記
前言
今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426
昨天的題解
每天一道leetcode-105從前序和中序序列構建二叉樹
題目
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意: 你可以假設樹中沒有重複的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹：
題目詳解
思路
- 我們首先要得到從前序序列中獲取根節點，然後遍歷中序序列，找到根節點的位置，以此直到其左子樹和右子樹的範圍。 當我得到其左子樹之後，事情就開始重複了，我們仍然需要根據前序序列中找到這顆左子樹的根節點，然後再根據中序序列得到這顆左子樹根節點的左右子樹,就這樣一直重複這個過程，直到，左子樹只有一個節點，那麼也就是在遞歸的最深的那一層，這時候就把這個節點返回，然後就一層層回溯，這樣就完成了左子樹的構建
- 對於右子樹也是同理。
代碼
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //寫法仿照 劍指offer 面試題7 重建二叉樹 public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null || preorder.length==0){ return null; } return buildCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } private TreeNode buildCore(int[] preorder,int preSt,int preEnd,int[] inorder,int inSt,int inEnd){ //前序遍歷第一個節點是根節點 int rootValue = preorder[preSt]; TreeNode root = new TreeNode(rootValue); //前序序列只有根節點 if(preSt == preEnd){ return root; } //遍歷中序序列，找到根節點的位置 int rootInorder = inSt; while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){ rootInorder++; } //左子樹的長度 int leftLength = rootInorder - inSt; //前序序列中左子樹的最後一個節點 int leftPreEnd = preSt + leftLength; //左子樹非空 左子樹長度大於等於0 if(leftLength>0){ //重建左子樹 root.left = buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,inEnd); } //右子樹非空 preEnd 和prest是前序數組的結尾和開頭，相減就是長度，如果左子樹長度小於整個長度 //那麼說明右子樹肯定 存在。那麼對右子樹也進行同樣的構建樹的操作。 if(leftLength < preEnd - preSt){ //重建右子樹 root.right = buildCore(preorder,leftPreEnd +1,preEnd,inorder,rootInorder+1,inEnd); } return root; } }
代碼截圖（避免亂碼）
