資訊專欄INFORMATION COLUMN
Problem
Given a binary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/
9 20
/
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]Note
用先入先出的Queue。用size標(biāo)記每一層的結(jié)點(diǎn)數(shù)目并定向循環(huán)。
Solutionclass Solution {
public List> levelOrder(TreeNode root) {
List> res = new ArrayList<>();
if (root == null) return res;
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
temp.add(cur.val);
}
res.add(temp);//for traversal II: res.add(0, temp);
}
return res;
}
}
DFS
class Solution {
public List> levelOrder(TreeNode root) {
List> res = new ArrayList<>();
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode root, int level, List> res) {
if (root == null) return;
if (level >= res.size()) res.add(new ArrayList()); //level >= res.size() ---- from 0 >= 0 to initialize
res.get(level).add(root.val);
dfs(root.left, level+1, res);
dfs(root.right, level+1, res);
}
}
public class Solution {
public ArrayList> levelOrderBottom(TreeNode root) {
ArrayList> res = new ArrayList<>();
if (root == null) return res;
helper(root, res, 0);
return res;
}
public void helper(TreeNode root, ArrayList> res, int index) {
int size = res.size();
if (index == size) {
ArrayList curList = new ArrayList<>();
curList.add(root.val);
res.add(0, curList);
}
else res.get(size-index-1).add(root.val);
if (root.left != null) helper(root.left, res, index+1);
if (root.right != null) helper(root.right, res, index+1);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/66025.html
Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
Problem Flatten a binary tree to a fake linked list in pre-order traversal.Here we use the right pointer in TreeNode as the next pointer in ListNode. Example 1 1 ...
摘要：根據(jù)二叉平衡樹的定義，我們先寫一個(gè)求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...
Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...
閱讀 3791·2021-10-12 10:11
閱讀 2049·2019-08-30 15:53
閱讀 1649·2019-08-30 13:15
閱讀 2360·2019-08-30 11:25
閱讀 1882·2019-08-29 11:24
閱讀 1721·2019-08-26 13:53
閱讀 3609·2019-08-26 13:22
閱讀 1861·2019-08-26 10:24
