資訊專(zhuān)欄INFORMATION COLUMN
摘要：思路在的順序里，先，然后再左右。所以根據(jù)可以知道的。接著再分別在和的里面重復(fù)找以及左右的過(guò)程。首先的包括和，以及對(duì)應(yīng)的起始和結(jié)束位置，對(duì)應(yīng)的起始和結(jié)束位置。返回值為，因?yàn)槊總€(gè)里要一個(gè)，同時(shí)找到它的和，左右節(jié)點(diǎn)通過(guò)返回值獲得。同時(shí)的不需要了。
From Preorder and Inorder
思路
在preorder的順序里，先root，然后再左右。所以根據(jù)preorder可以知道root的。而在inorder的順序里，是先左再root再右，所以在inorder里找到root之后就可以知道left和right分別有多少。接著再分別在left和right的subarray里面重復(fù)找root以及左右的過(guò)程。
dfs
首先dfs的argument包括preorder和inorder，以及preorder對(duì)應(yīng)的起始和結(jié)束位置，inorder對(duì)應(yīng)的起始和結(jié)束位置。返回值為T(mén)reeNode，因?yàn)槊總€(gè)recursion里要new一個(gè)root，同時(shí)找到它的left和right，左右節(jié)點(diǎn)通過(guò)返回值獲得。
cache提高速度
每次recursion里都要在inorder里找到root對(duì)應(yīng)的位置，直接遍歷復(fù)雜度是O(N)，可以事先用一個(gè)全局的map來(lái)保存位置，這樣復(fù)雜度下降到O(1)。同時(shí)dfs的argument不需要inorder了。
public TreeNode buildTree(int[] preorder, int[] inorder) {
/* 1. find the index of root in inorder (1st in preorder)
* 2. all left are nodes in left subtree, right are in right subtree
* 3. recursively
*/
if(preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0 || preorder.length != inorder.length) return null;
// cache
map = new HashMap();
for(int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
return dfs(preorder, 0, preorder.length-1, 0, inorder.length - 1);
}
// the corresponding index in inorder
Map map;
private TreeNode dfs(int[] pre, int ps, int pe, int is, int ie) {
// base cases
if(ps > pe || is > ie) return null;
TreeNode root = new TreeNode(pre[ps]);
int index = map.get(root.val);
// left and right
root.left = dfs(pre, ps + 1, ps + index - is, is, index-1);
root.right = dfs(pre, ps + index - is + 1, pe, index+1, ie);
return root;
}
From Inorder and Postorder
和preorder的差不多，postorder里面root位置變一下，改成最后一個(gè)。
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap();
for(int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
return dfs(postorder, 0, postorder.length - 1, 0, inorder.length - 1);
}
Map map;
private TreeNode dfs(int[] post, int ps, int pe, int is, int ie) {
// base case
if(ps > pe || is > ie) return null;
TreeNode root = new TreeNode(post[pe]);
int index = map.get(root.val);
root.left = dfs(post, ps, ps + index - is - 1, is, index - 1);
root.right = dfs(post, ps + index - is, pe - 1, index + 1, ie);
return root;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66480.html
摘要：二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹(shù)，后半部分是根的右子樹(shù)。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過(guò)，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要：解題思路利用遞歸思想，先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn)，然后在中序遍歷中尋找該節(jié)點(diǎn)，該節(jié)點(diǎn)左邊的就是左子樹(shù)，右邊的是右子樹(shù)。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：棧迭代復(fù)雜度時(shí)間空間遞歸?？臻g對(duì)于二叉樹(shù)思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的存儲(chǔ)遍歷到節(jié)點(diǎn)，替代遞歸中的進(jìn)程棧，實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷，我們出棧頂節(jié)點(diǎn)，記錄它的值，然后將它的左右子節(jié)點(diǎn)入棧，以此類(lèi)推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...
閱讀 3275·2023-04-25 22:47
閱讀 3790·2021-10-11 10:59
閱讀 2317·2021-09-07 10:12
閱讀 4274·2021-08-11 11:15
閱讀 3442·2019-08-30 13:15
閱讀 1760·2019-08-30 13:00
閱讀 979·2019-08-29 14:02
閱讀 1699·2019-08-26 13:57
