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