大型门户网站开发,滁州做网站的,黑龙江省建设工程交易中心网站,韩国电信 网站题目描述
从上到下按层打印二叉树#xff0c;同一层的节点按从左到右的顺序打印#xff0c;每一层打印到一行。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果#xff1a; [3,9,20,15,7] 提示#xff1a;
节… 题目描述
从上到下按层打印二叉树同一层的节点按从左到右的顺序打印每一层打印到一行。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果 [3,9,20,15,7] 提示
节点总数 1000 思路 这个题目的意思很明确就是从根节点开始一层一层打印节点而且节点顺序是从左到右。以上面示例为例3为根节点之后打印它的左右节点920之后再打印20的子节点157。全部打印完成结束。 这道题有点类似图算法中的广度优先搜索先从顶端开始依次遍历图的下一层节点下一层节点遍历完成接着遍历下下一层。仅仅依赖树结构的左右节点关系然后递归遍历我们无法得到最终结果因为随着层数的增加兄弟节点之间没有必然关系他们无法保证从左到右来遍历。 这里我们需要借助一个队列来存放遍历过的节点这样每遍历依次后续的遍历我们从队列开头取元素这样就可以保证按照层级和左右顺序来打印树节点。 代码
package com.xxx.example;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Offer32PrintTreeNode {private static TreeNode root;private static ListListInteger nodeList new ArrayList();public static void main(String[] args) {TreeNode treeNode new TreeNode(3);TreeNode treeNode1 new TreeNode(9);TreeNode treeNode2 new TreeNode(20);TreeNode treeNode3 new TreeNode(15);TreeNode treeNode4 new TreeNode(7);root treeNode;treeNode2.left treeNode3;treeNode2.right treeNode4;root.left treeNode1;root.right treeNode2;int[] result levelOrder(root);for(int i0;iresult.length;i) {System.out.print(result[i] );}System.out.println();}public static int[] levelOrder(TreeNode root) {if (root null)return new int[0];QueueTreeNode queue new LinkedList();ArrayListInteger list new ArrayList();queue.add(root);while (!queue.isEmpty()) {TreeNode curNode queue.poll();list.add(curNode.val);if (curNode.left ! null)queue.add(curNode.left);if (curNode.right ! null)queue.add(curNode.right);}return list.stream().mapToInt(Integer::intValue).toArray();}}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int value) {this.val value;this.left null;this.right null;}Overridepublic String toString() {return val ;}
}还有一种办法其实就是利用深度优先搜索的思想解决这个似乎有点玄妙这里明明是要广度优先搜索怎么还利用起深度优先搜索呢其实是这样的这里按照深度优先搜索我们只是把搜到的数据打上标签这个标签就是它的层次也叫深度每个深度的节点我们保存到同样深度的map映射里。最后我们遍历map得到所有按照层次组织的节点这样就是从上到下从左到右打印二叉树节点。 深度优先搜索 package com.xxx.tutorial;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TreeNodeTraversal {private static MapInteger, ListInteger map new HashMap();private static int max -1;private static int cnt 0;public static void main(String[] args) {TreeNode node0 new TreeNode(3);TreeNode node1 new TreeNode(9);TreeNode node2 new TreeNode(20);TreeNode node3 new TreeNode(15);TreeNode node4 new TreeNode(7);node0.left node1;node0.right node2;node2.left node3;node2.right node4;int[] res traversal(node0);for (int i 0; i res.length; i) {System.out.print(res[i] );}System.out.println();}public static int[] traversal(TreeNode root) {dfs(root, 0);int[] ans new int[cnt];for (int i 0, idx 0; i max; i) {for (int x : map.get(i))ans[idx] x;}return ans;}public static void dfs(TreeNode node, int depth) {if (node null) return;max Math.max(max, depth);cnt;dfs(node.left, depth 1);ListInteger list map.getOrDefault(depth, new ArrayList());list.add(node.val);map.put(depth, list);dfs(node.right, depth 1);}public static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int value) {this.val value;this.left null;this.right null;}}
}这里通过递归调用我们能遍历完所有节点并按照深度层次保存各自深度的节点。 这个思路很巧妙它利用深度层次来映射对应的节点最后我们遍历map映射得到所有节点他们的顺序正好是从上到下从左到右。 剑指offer打印二叉树还有另一个题目就是按照层次打印二叉树就是[[3],[9,20],[15,7]]相信经过上面的深度优先搜索大家也许有一些想法这个代码或许简单改造一下就可以了。
