signed

QiShunwang

“诚信为本、客户至上”

LeetCode---树的层次遍历

2021/3/21 11:42:31   来源:

文章目录

  • 637.二叉树的层平均值
    • 题目大意
    • 解题思路
    • 代码实现
  • 513.找树左下角的值
    • 题目描述
    • 解题思路
    • 代码实现
  • 144.二叉树的前序遍历
    • 题目大意
    • 解题思路
    • 代码实现
  • 145.二叉树的后序遍历
    • 题目大意
    • 解题思路
    • 代码实现
  • 94.二叉树的中序遍历
    • 题目大意
    • 解题思路
    • 代码实现

637.二叉树的层平均值

题目大意

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
在这里插入图片描述

解题思路

(一)BFS
利用一个队列来存放每层的数字。
队列的创建:

Queue<TreeNode> queue=new LinkedList<>();

(二)DFS

代码实现

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //存放结果的
        List<Double> res=new ArrayList<>();
        //创建一个队列用于存放每层的数字
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            double sum=0;
            int cnt=queue.size();
            for(int i=0;i<cnt;i++){
                TreeNode node=queue.poll();
                sum+=node.val;
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(sum/cnt);
        }
        return res;
    }
}

(二)DFS
利用递归来解决:
分别创建三个集合来存储每层的节点数、每一层的节点之和以及最终的结果。
递归的求每一层的节点之和和节点数:

dfs(root,level,count,sum);

其中的level表示第几层。如果层数小于sum中元素的个数,就表示该层已经有数加入了,那么就将当前的值加入到已有的值上,反之就作为该层的第一个值,加入到sum集合中。递归的计算左右子树下一层。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //用于存放每层的节点数
        List<Integer> count=new ArrayList<>();
        //用于存放每一层的节点之和
        List<Double> sum=new ArrayList<>();
        //用于存放结果
        List<Double> ave=new ArrayList<>();
        dfs(root,0,count,sum);
        for(int i=0;i<sum.size();i++){
            ave.add(sum.get(i)/count.get(i));
        }
        return ave;     
    }
    public void dfs(TreeNode root,int level,List<Integer> count,List<Double> sum){
        if(root==null){
            return ;
        }
        //如果每一层已经有点加入计算该层的和,那么也将目前的值加到之前的值上
        if(level<sum.size()){
            sum.set(level, sum.get(level) + root.val);
            count.set(level,count.get(level)+1);
        }else{//如果是该层的第一个值计算
            sum.add(1.0*root.val);
            count.add(1);
        }
        //递归计算下一层
        dfs(root.left,level+1,count,sum);
        dfs(root.right,level+1,count,sum);
    }
}

513.找树左下角的值

题目描述

给定一个二叉树,在树的最后一行找到最左边的值。
在这里插入图片描述

解题思路

该题的重点在于先将右子树加入队列,再将左子树加入队列,这样最后得出的就是最后一层的左子树了。

代码实现

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root=queue.poll();
            if(root.right!=null){
                queue.add(root.right);
            }
            if(root.left!=null){
                queue.add(root.left);
            }  
        }
        return root.val;
    }
}

144.二叉树的前序遍历

题目大意

给你二叉树的根节点 root ,返回它节点值的前序遍历。
在这里插入图片描述

解题思路

二叉树的前序遍历是根节点–左子树–右子树。
(一) 递归
隐式维护了一个栈。
时间复杂度:O(n),n是二叉树的节点数,每一个节点恰好被遍历一遍。
空间复杂度:O(n),为递归过程中栈的调用,平均情况下为O(nlogn),最坏情况下树呈链状,为O(n)。
(二)迭代
采用栈结构,后进的先遍历,先将右子树加入,再将左子树加入。
时间复杂度:O(n),每一个节点恰好被遍历一遍。
空间复杂度:O(n),为迭代过程中显示栈的开销,平均情况下为O(nlogn),最坏情况下树呈链状,为O(n)。
(三)Morris遍历(没看懂
可实现在线性时间内,只占用常数空间来实现前序遍历。
核心思想是利用树的大量的空闲指针,实现空间开销的极限缩减,前序遍历的规则如下:

  1. 新建临时节点,令该节点为root。
  2. 如果当前节点的左子节点为空,将当前节点加入答案,并遍历当前节点的右子节点
  3. 如果当前节点的左子节点不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点:
    (1)如果前驱节点的右子节点为空,将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案,并将前驱节点的右子节点更新为当前节点,当前节点更新为当前节点的左子节点。
    (2)如果前驱节点的右子节点为当前节点,将他的右子节点重新设置为空。当前节点更新为当前节点的右子节点。
  4. 重复步骤2和步骤3,直到遍历结束。

代码实现

(一)递归实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //递归实现
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root,List<Integer> res){
        if(root==null){
            return ;
        }
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }
}

(二)迭代实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //非递归实现前序遍历
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        //创建一个栈 先进后出
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
            res.add(node.val);
        }
        return res;
    }
}

(三)Morris 遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        TreeNode p1 = root, p2 = null;

        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    res.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                res.add(p1.val);
            }
            p1 = p1.right;
        }
        return res;
    }
}

145.二叉树的后序遍历

题目大意

给定一个二叉树,返回它的后序遍历。
在这里插入图片描述

解题思路

(一)递归实现
后序遍历的顺序为:左子树->右子树->根节点
(二)迭代实现
按照后序遍历的相反顺序根->右->左的顺序进行遍历,然后将遍历的结果进行翻转即可得到后序遍历的顺序。

代码实现

(一)递归实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //递归实现二叉树的后续遍历
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        postorder(root,res);
        return res;
    }
    public void postorder(TreeNode root,List<Integer> res){
        if(root==null){
            return ;
        }
        postorder(root.left,res);
        postorder(root.right,res);
        res.add(root.val);
    }
}

(二)迭代实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //非递归实现二叉树的后续遍历 左--右--中
        List<Integer> res=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            res.add(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

94.二叉树的中序遍历

题目大意

给定一个二叉树的根节点 root ,返回它的中序遍历。
在这里插入图片描述

解题思路

(一)递归实现
中序遍历:左子树->根节点->右子树
(二)迭代实现

代码实现

(一)递归实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //递归实现 中序:左->中->右
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode root,List<Integer> res){
        if(root==null){
            return ;
        }
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
    }
}

(二)迭代实现
当前节点不为空或者栈不为空时进入循环:
当前节点不为空控制着看他是否存在左子树找左子树上的节点,如果当前节点为空了就去栈中找。首先一直找左节点,左节点为空时,就在栈中退出元素,继续找元素的右孩子,继而继续找右孩子的左节点,按照和之前的方式进行遍历。重点是cur节点的设置

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //迭代实现 中序:左->中->右
        List<Integer> res=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return res;
        }
        TreeNode cur=stack.push(root);
        //当前节点不为空或者栈不为空时进入循环
        //当前节点不为空控制着看他是否存在左子树找左子树上的节点
        //如果当前节点为空了就去栈中找
        while(cur!=null||!isEmpty(stack)){
            //一直找左子树节点,如果还存在左子树就将当前节点压栈
            while(cur!=null){
                stack.push(cur);
                cur=cur.left; 
            }
            TreeNode node=stack.pop();
            res.add(node.val);
            cur=node.right;
        }
        return res;   
    }
}