【問題描述】[中等]

【解答思路】

copyOfRange

class Solution {public TreeNode constructFromPrePost(int[] pre, int[] post) {if(pre==null || pre.length==0) {return null;}return dfs(pre,post);}private TreeNode dfs(int[] pre,int[] post) {if(pre==null || pre.length==0) {return null;}//數(shù)組長度為1時，直接返回即可if(pre.length==1) {return new TreeNode(pre[0]);}//根據(jù)前序數(shù)組的第一個元素，創(chuàng)建根節(jié)點 TreeNode root = new TreeNode(pre[0]);int n = pre.length;for(int i=0;i<post.length;++i) {if(pre[1]==post[i]) {//根據(jù)前序數(shù)組第二個元素，確定后序數(shù)組左子樹范圍int left_count = i+1;//拆分前序和后序數(shù)組，分成四份int[] pre_left = Arrays.copyOfRange(pre,1,left_count+1);int[] pre_right = Arrays.copyOfRange(pre,left_count+1,n);int[] post_left = Arrays.copyOfRange(post,0,left_count);int[] post_right = Arrays.copyOfRange(post,left_count,n-1);//遞歸執(zhí)行前序數(shù)組左邊、后序數(shù)組左邊root.left = dfs(pre_left,post_left);//遞歸執(zhí)行前序數(shù)組右邊、后序數(shù)組右邊root.right = dfs(pre_right,post_right);break;}}//返回根節(jié)點return root;} } 作者：wang_ni_ma 鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solution/tu-jie-889-gen-ju-qian-xu-he-hou-xu-bian-li-gou-2/

【總結(jié)】

1.前中后序遍歷變化的是[中]的位置，左到右的順序不改變

• 前序遍歷 中左右
• 中序遍歷 左中右
• 后續(xù)遍歷 左右中

2.還原二叉樹 借助HashMap or copyOfRange

根據(jù)前序和后序遍歷構(gòu)造二叉樹
[Leetcode][第889題][JAVA][根據(jù)前序和后序遍歷構(gòu)造二叉樹][分治][遞歸]
前序+中序遍歷可畫出原二叉樹
[Leedcode][JAVA][第105題][從前序與中序遍歷序列構(gòu)造二叉樹][棧][遞歸][二叉樹]
后續(xù)+中序遍歷可畫出原二叉樹
[Leetcode][第106題][JAVA][ 從中序與后序遍歷序列構(gòu)造二叉樹][分治][遞歸]

3. 多畫圖 寫寫寫 遍歷代碼 手撕變量 大腦保持清醒

總結(jié)

以上是生活随笔為你收集整理的[Leetcode][第889题][JAVA][根据前序和后序遍历构造二叉树][分治][递归]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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