查 网站接入服务提供者名称,济南app网站建设,西安专业做网站建,淘宝补流量平台【问题描述】[第102题][二叉树的层序遍历][中等]
给你一个二叉树#xff0c;请你返回其按 层序遍历 得到的节点值。 #xff08;即逐层地#xff0c;从左到右访问所有节点#xff09;。示例#xff1a;
二叉树#xff1a;[3,9,20,null,null,15,7],3/ \9 20/ \15 7
返…【问题描述】[第102题][二叉树的层序遍历][中等]
给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。示例
二叉树[3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回其层次遍历结果[[3],[9,20],[15,7]
]
【解答思路】
典型BFS
1.队列
一层一层入队统计每层数量当前层出队下一层入队 时间复杂度O(N^2) 空间复杂度O(1) class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if (root null) return res;DequeTreeNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()) {ListInteger tmp new ArrayList();//每一层的数量int cnt queue.size();for (int i 0; i cnt; i) {TreeNode node queue.poll();// System.out.println(node.val);tmp.add(node.val);if (node.left ! null) queue.add(node.left);if (node.right ! null) queue.add(node.right);}//所有出完之后 添加listres.add(tmp);}return res;}
}
2. 递归 helper(res, root, 0); 0代表层数 也代表列表的下标 时间复杂度O(N) 空间复杂度O(1) class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();helper(res, root, 0);return res;}private void helper(ListListInteger res, TreeNode root, int depth) {if (root null) return;if (res.size() depth) res.add(new LinkedList());res.get(depth).add(root.val);helper(res, root.left, depth 1);helper(res, root.right, depth 1);}
}
【总结】
1.模板
DFS 遍历使用递归
void dfs(TreeNode root) {if (root null) {return;}dfs(root.left);dfs(root.right);
}BFS遍历使用模板层次遍历 最短路径
void bfs(TreeNode root) {QueueTreeNode queue new ArrayDeque();queue.add(root);while (!queue.isEmpty()) {TreeNode node queue.poll(); // Java 的 pop 写作 poll()if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}
}
2.二叉树遍历
前序遍历 先输出当前结点的数据再依次遍历输出左结点和右结点 中序遍历 先遍历输出左结点再输出当前结点的数据再遍历输出右结点 后续遍历 先遍历输出左结点再遍历输出右结点最后输出当前结点的数据 参考链接https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/di-gui-he-die-dai-by-powcai-2/
