資訊專欄INFORMATION COLUMN
摘要：題目鏈接這道題要求的來(lái)保存結(jié)果，一開始想到的是用遍歷的時(shí)候更新，比如現(xiàn)在的，有左孩子的話就在最前面插入結(jié)果，且。不過(guò)這樣的話每個(gè)的時(shí)間是了。還需要遍歷從而得到要求的結(jié)果，因?yàn)闆](méi)有，所以還需要保存下的最小值和最大值，從而知道遍歷的范圍。
314. Binary Tree Vertical Order Traversal
題目鏈接：https://leetcode.com/problems...
這道題要求vertical的order來(lái)保存結(jié)果，一開始想到的是用遍歷的時(shí)候更新index，比如現(xiàn)在的index = 0，有左孩子的話就在最前面插入結(jié)果，且shift++。不過(guò)這樣的話每個(gè)subproblem的時(shí)間是O(N)了。
那么可以先用hashmap來(lái)cache，遍歷的時(shí)候就要根據(jù)node所在的column的index來(lái)存，根節(jié)點(diǎn)的index從0開始，左邊的孩子index-1，右邊的孩子index+1，遍歷樹結(jié)束之后可以把所有index已經(jīng)對(duì)應(yīng)的值保存下來(lái)。還需要遍歷hashmap從而得到要求的結(jié)果，因?yàn)閔ashmap沒(méi)有order，所以還需要保存下index的最小值和最大值，從而知道hashmap遍歷的范圍。第一遍tree的遍歷可以bfs也可以dfs。
public class Solution {
public List> verticalOrder(TreeNode root) {
// store the val according to their index in col
map = new HashMap();
List> result = new ArrayList();
if(root == null) return result;
// traverse the tree
bfs(root);
// traverse map to get result
for(int i = low; i <= high; i++) {
if(map.containsKey(i)) {
result.add(map.get(i));
}
}
return result;
}
Map> map;
int low = 0, high = 0;
private void bfs(TreeNode root) {
// bfs, use queue
Queue q = new LinkedList();
Queue index = new LinkedList();
q.offer(root);
index.offer(0);
while(!q.isEmpty()) {
TreeNode cur = q.poll();
int curIndex = index.poll();
// add node according to the column index
if(!map.containsKey(curIndex)) map.put(curIndex, new ArrayList());
map.get(curIndex).add(cur.val);
// update lowest index and highes index
low = Math.min(low, curIndex);
high = Math.max(high, curIndex);
if(cur.left != null) {
q.offer(cur.left);
index.offer(curIndex - 1);
}
if(cur.right != null) {
q.offer(cur.right);
index.offer(curIndex + 1);
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66649.html
摘要：棧迭代復(fù)雜度時(shí)間空間遞歸?？臻g對(duì)于二叉樹思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的存儲(chǔ)遍歷到節(jié)點(diǎn)，替代遞歸中的進(jìn)程棧，實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷，我們出棧頂節(jié)點(diǎn)，記錄它的值，然后將它的左右子節(jié)點(diǎn)入棧，以此類推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...
摘要：解題思路層次遍歷二叉樹，我們采用隊(duì)列，本題的注意點(diǎn)是需要分割出每一層的序列，所以在從隊(duì)列中取元素之前，我們要先記錄隊(duì)列的大小，以表示這一層中節(jié)點(diǎn)的個(gè)數(shù)。 Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes values. (ie, from...
429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...
摘要：題目要求對(duì)于一棵樹進(jìn)行序遍歷。水平遍歷即遍歷結(jié)束當(dāng)前行以后再遍歷下一行，并將每行的結(jié)果按行填入到數(shù)組中返回。利用水平遍歷的話，我們只需要知道當(dāng)前元素在樹中的高度就可以知道應(yīng)當(dāng)插入到那個(gè)數(shù)組中。 題目要求 Given a binary tree, return the level order traversal of its nodes values. (ie, from left to...
102. 二叉樹的層次遍歷 題目描述 給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。 （即zhucengde，從左到右訪問(wèn)）。 例如: 給定二叉樹: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其層次遍歷結(jié)果為： [ [3], [9,20], [15,7] ] class Solution: def le...
閱讀 3826·2021-11-24 10:23
閱讀 2834·2021-09-06 15:02
閱讀 1348·2021-08-23 09:43
閱讀 2418·2019-08-30 15:44
閱讀 3115·2019-08-30 13:18
閱讀 839·2019-08-23 16:56
閱讀 1808·2019-08-23 16:10
閱讀 607·2019-08-23 15:08
