1. 深度优先算法
class Solution{public List<List<Integer>> levelOrder(TreeNode root){List<List<Integer>> result = new ArrayList<>() ;if (root != null){ // 如果这是一个空的二叉树dfs(result, root, 0) ;}return result ;}// 通过leve来记录节点所在的层private void dfs(List<List<Integer>> result, TreeNode node, int level){// 当读入一个新的深度时if (result.size() - 1 < level){result.add(new ArrayList<Integer>()) ;}// 加入当前的节点值result.get(level).add(node.val) ;// 如果左节点不为空if (node.left != null){// 遍历所有的左节点---深度+1dfs(result, node.left, level + 1) ;}// 如果右节点不为空if (node.right != null){// 遍历所有的右节点---深度 + 1dfs(result, node.right, level + 1) ; }}}
2. 广度优先算法
public class Solution {/*** * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>>*/public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {// write code hereArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();if (root == null){return result;}// 0.创建一个队列Queue<TreeNode> queue = new LinkedList<TreeNode>();// 1.将根节点放进去[第一层节点]queue.offer(root);// 队列为空退出循环while (!queue.isEmpty()){int size = queue.size(); // 记住当前层node的个数// 2.新建list用来记录每一层的数据ArrayList<Integer> list = new ArrayList<Integer> ();// 遍历上一层的节点并放入下一层的节点for (int i = 0; i < size; i ++){// 3.当前队列出栈放入listTreeNode node = queue.poll();list.add(node.val);// 4. 当前的queue出队列并遍历该节点的左右子节点放入队列if (node.left != null){queue.offer(node.left);}if (node.right != null){queue.offer(node.right);}}// 5.将当前层所有的node.val放入result中result.add(list);}return result;}}
作者:nettee
链接:https://leetcode-/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
来源:力扣(LeetCode)
如果觉得《二叉树深度优先广度优先算法》对你有帮助,请点赞、收藏,并留下你的观点哦!