面试题32 - III. 从上到下打印二叉树 III
2024-10-08 06:08:30
面试题32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
- 节点总数 <= 1000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
两个栈
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
Stack<TreeNode> oddstack = new Stack<>();
Stack<TreeNode> evenstack = new Stack<>();
List<Integer> list;
oddstack.add(root);
while (!oddstack.isEmpty() || !evenstack.isEmpty()) {
list = new ArrayList<>();
while (!oddstack.isEmpty()) {
TreeNode node = oddstack.pop();
list.add(node.val);
TreeNode leftnode = node.left;
if(leftnode != null) {
evenstack.add(leftnode);
}
TreeNode rightnode = node.right;
if(rightnode != null) {
evenstack.add(rightnode);
}
}
res.add(list);
list = new ArrayList<>();
while (!evenstack.isEmpty()) {
TreeNode node = evenstack.pop();
list.add(node.val);
TreeNode rightnode = node.right;
if(rightnode != null) {
oddstack.add(rightnode);
}
TreeNode leftnode = node.left;
if(leftnode != null) {
oddstack.add(leftnode);
}
}
if(list.size() != 0) {
res.add(list);
}
}
return res;
}
参考
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
helper(root, 0);
return res;
}
private void helper(TreeNode root, int level) {
if (root == null)
return;
if (res.size() == level) {
res.add(new ArrayList<>());
}
if (level % 2 == 0) {
res.get(level).add(root.val);
} else {
// 加在最前面
res.get(level).add(0, root.val);
}
helper(root.left, level + 1);
helper(root.right, level + 1);
}
官方题解
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}
作者:LeetCode
链接:https://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
最新文章
- java 配置环境变量
- SVN迁移到Git的过程(+ 一些技巧
- jQuery的deferred对象
- Css_加载样式
- 人见人爱a*b 杭电2035
- (Problem 47)Distinct primes factors
- Palindromes _easy version
- httpd的简单配置(转)
- JSP内置对象--application对象(getRealPath(),getAttributeNames(),getContextPath())
- Ionic在Android上部署app步骤
- Linux学习笔记(二)——文件/目录/VIM
- TxDragon的训练5
- Vue.js-04:第四章 - 页面元素样式的设定
- JVM系列第12讲:JVM参数之查看JVM参数
- 20190423 PowerDesigner 数据库模型快速建立
- Spark笔记
- 转:Jmeter分布式测试
- Delphi窗体之间互相调用的简单问题
- 使用 mod_rewrite 来修改 Confluence 6 的 URLs
- java代码理解