[LC] 314. Binary Tree Vertical Order Traversal
2024-09-07 05:46:04
Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples 1:
Input:[3,9,20,null,null,15,7]
3
/\
/ \
9 20
/\
/ \
15 7 Output: [
[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 {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
dfs(root, 0);
for (int i = min; i <= max; i++) {
res.add(new ArrayList<>());
} Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> indexQ = new LinkedList<>();
queue.offer(root);
// map the leftmost to 0, so that root is -min
indexQ.offer(-min);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
int curIndex = indexQ.poll();
res.get(curIndex).add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
indexQ.offer(curIndex - 1);
}
if (cur.right != null) {
queue.offer(cur.right);
indexQ.offer(curIndex + 1);
}
}
return res;
} private void dfs(TreeNode root, int num) {
if (root == null) {
return;
}
min = Math.min(min, num);
max = Math.max(max, num);
dfs(root.left, num - 1);
dfs(root.right, num + 1);
} }
最新文章
- js学习心得之思维逻辑与对象上下文环境(一)
- Wiki介绍
- webStorage和cookie的区别
- Android学习
- IT客学院《构建高转化率的着陆页-PS+HTML+网络营销》共25节【价值199元】无水印版
- 经历:如何设置jquery easyui中下拉框不可编辑
- MOUNT MACBOOK DISK (OSX / HFS+) ON UBUNTU 12.04 LTS WITH READ/WRITE
- Visual Studio GitHub For Windows部署
- 编程算法 - 二叉树的深度 代码(C)
- .NET依托CLR进行的内存的管理
- PHP字符串转义
- C#-判断Shift,Alt,Ctrl是否被按下,确定所按下的组合键
- PowerDesigner设置null约束
- Qt 的一些浅知识点
- Jenkins配置从节点
- Flask简介&;入门
- Putty6.0 提示Access denied
- mkpasswd命令
- springboot使用遇到问题:Class “model.Address” is listed in the persistence.xml file but not mapped
- Error creating bean with name &#39;enableRedisKeyspaceNotificationsInitializer&#39; defined in class path resource