LeetCode 102. 二叉树的层序遍历

雨点打透心脏的1/2处 2022-12-23 09:47 135阅读 0赞

### LeetCode 102. 二叉树的层序遍历 ###

*  题目：
 *  解题方法：
 *   *  方法1：BFS（广度优先搜索）
     *   *  Java实现
     *  方法2：DFS（深度优先搜索）
     *   *  Java实现

# 题目： #

[LeetCode 102. 二叉树的层序遍历][LeetCode 102.]  
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。  
**示例：**  
二叉树：\[3,9,20,null,null,15,7\],  
![>    3/  9  20/  15   7][3_ 9 20_ 15 7]

返回其层次遍历结果：

> \[  
> \[3\],  
> \[9,20\],  
> \[15,7\]  
> \]

# 解题方法： #

## 方法1：BFS（广度优先搜索） ##

### Java实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            
            List<List<Integer>> allResults = new ArrayList<>();
            if (root == null) { return allResults; }
            Queue<TreeNode> queue = new LinkedList<>();
    
            queue.offer(root);
            while (!queue.isEmpty()) {
                List<Integer> resuts = new ArrayList<>();
                int levelNum = queue.size();
    
                
                for (int i = 0; i < levelNum; ++i) {
                    TreeNode node = queue.poll();
                    resuts.add(node.val);
                    if (node.left != null) { queue.offer(node.left); }
                    if (node.right != null) { queue.offer(node.right); }
                }
                allResults.add(resuts);
            }
            return allResults;
        }
    }

## 方法2：DFS（深度优先搜索） ##

### Java实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            
            List<List<Integer>> allResults = new ArrayList<>();
            if (root == null) { return allResults; }
            dfs(root, 0, allResults);
            return allResults;
        }
    
        public void dfs(TreeNode root, int level, List<List<Integer>> allResults) {
            if (level == allResults.size()) {
                allResults.add(new ArrayList<>());
            }
            allResults.get(level).add(root.val);
            if (root.left != null) { dfs(root.left, level + 1, allResults); }
            if (root.right != null) { dfs(root.right, level + 1, allResults); }
        }
    }

[LeetCode 102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[3_ 9 20_ 15 7]: /images/20221120/d9940d0e531d4672977b089872ef761b.png