leetcode算法练习【107】二叉树的层次遍历 II

爱被打了一巴掌 2023-02-14 07:48 13阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
    
    例如：
    给定二叉树 [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    返回其自底向上的层次遍历为：
    
    [
      [15,7],
      [9,20],
      [3]
    ]

#### 方案： ####

*  思路同102，数组倒过来存即可

/** * 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>> levelOrderBottom(TreeNode root) { 
                // 层序
                int size = 1;
                TreeNode tmp;
                //利用队列来实现层序遍历
                LinkedList<TreeNode> list = new LinkedList<>(); 
                List<List<Integer>> res = new LinkedList<>();
                if(root==null) return res;
                list.add(root);
                while(list.size()>0){ 
                    //开始遍历
                    List<Integer> nums = new LinkedList<>();
                    size = list.size();
                    for(int i =0;i<size;i++){ 
                        tmp = list.removeFirst();
                        //如果还有下一层，那就入队
                        if(tmp.left!=null) { list.add(tmp.left);}
                        if(tmp.right!=null) { list.add(tmp.right);}
                        nums.add(tmp.val);
                    }
                    res.add(0,nums);
                }
                return res;
        }
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode