( Leetcode 刷题)二叉树的层序遍历、二叉树的锯齿形层次遍历、二叉树的层次遍历Ⅱ、N叉树的层序遍历

题目描述

102. 二叉树的层序遍历
给定一个二叉树，返回其按层序遍历得到的结点值。

解法1 递归

/**
 * 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>> list = new ArrayList<>();
        //处理输入空树
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        CX(1, root, list);
        return list;
    }

    public void CX(int level, TreeNode root, List<List<Integer>> list) {
        //在二维数组相应位置添加一维数组，用于存放对应层的结点值。
        //第一次进入函数时size = 0 < 1；在list 中添加存放第一层结点的数组，此后遍历过程中，充当在二位数组中添加数组的作用。list.size()是二维数组有多少个一位数组
        if (list.size() < level) {
            list.add(new ArrayList<Integer>());
        }
        //层数从1开始，二维数组从0开始，在相应层添加值
        list.get(level - 1).add(root.val);
        if (root.left != null) {
            CX(level + 1, root.left, list);
        }
        if (root.right != null) {
            CX(level + 1, root.right, list);
        }
    }
}

解法2 迭代

/**
 * 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>> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        //处理输入空
        if(root == null){
            return new ArrayList<List<Integer>>();
        }
        //将根结点加入队列，然后不断遍历队列
        queue.add(root);

        while (!queue.isEmpty()) {
            //同一层的结点放入同一个数组
            List<Integer> level = new ArrayList<>();
            int n = queue.size();
            //每完成一次0 ~ n 的for 循环，说明成功遍历了一层
            for (int i = 0; i < n; i++) {
                TreeNode curr = queue.poll();
                level.add(curr.val);
                //两个if 语句增加队列的长度，下一次从0 开始的for 循环时，队列里的元素数量刚好等于二叉树对应层的结点数量
                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
            }
            list.add(level);
        }
        return list;
    }
}

题目描述

给定一个二叉树，返回其结点值的锯齿形层次遍历。(即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行)。
103. 二叉树的锯齿形层次遍历

解法1 递归

与正常的层次遍历在偶数层(根结点为第一层)上不同，将正常的结果逆序即可。

/**
 * 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>> zigzagLevelOrder(TreeNode root) {
        boolean isold = true;
        //实施中会遇到在在队首添加元素，用LinkedList
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        if (root == null) {
            return list;
        }
        CX2(root, list, 1);
        return list;
    }

    public void CX2(TreeNode curr, List<List<Integer>> list, int level) {
        LinkedList<Integer> tmp = new LinkedList<>();
        if (list.size() < level) {
            list.add(new LinkedList<Integer>());
        }
        //奇数层正常添加，偶数层加在最前面
        if (level % 2 == 1) {
            list.get(level - 1).add(curr.val);
        } else {
            list.get(level - 1).add(0, curr.val);
        }
        if (curr.left != null) {
            CX2(curr.left, list, level + 1);
        }
        if (curr.right != null) {
            CX2(curr.right, list, level + 1);
        }
    }
}

解法2 迭代

维护一个队列，跟上面递归一样，注意顺序。

/**
 * 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>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1;
        //队列为空说明遍历完成
        while(!queue.isEmpty()){
            //申请一个临时数组存数
            List<Integer> tmp = new LinkedList<>();
            //实际 n 为每层的元素数量
            int n = queue.size();
            for(int i = 0; i < n ; i++){
                TreeNode p = queue.remove();
                if(level %2 == 1){
                    tmp.add(p.val);
                }else{
                //偶数层往数组最前方加数
                    tmp.add(0, p.val);
                }
                if( p.left != null){
                    queue.add(p.left);
                }
                if( p.right != null){
                    queue.add(p.right);
                }
            }
            list.add(tmp);
            level ++;
        }
        return list;
    }
}

题目描述

给定一个二叉树，返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)。
107. 二叉树的层次遍历 Ⅱ

解法1 递归

逆序正常层序遍历的结果

/**
 * 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) {
        List<List<Integer>> list = new ArrayList<>();
        int depth = 1;
        if (root == null) {
            return list;
        }
        CX(root, list, depth);
        Collections.reverse(list);
        return list;
    }

    public void CX(TreeNode root, List<List<Integer>> list, int depth) {
        int n = list.size();
        if (n < depth) {
            list.add(new ArrayList<Integer>());
        }
        list.get(depth - 1).add(root.val);
        if (root.left != null) {
            CX(root.left, list, depth + 1);
        }
        if (root.right != null) {
            CX(root.right, list, depth + 1);
        }
    }

}

解法2 迭代

把正常层序遍历得到的结果逆序一下。

/**
 * 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) {
        List<List<Integer>> list = new ArrayList();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode tmp = queue.poll();
                a.add(tmp.val);
                if (tmp.left != null) {
                    queue.add(tmp.left);
                }
                if (tmp.right != null) {
                    queue.add(tmp.right);
                }
            }
            list.add(a);
            //或者 list.add(0,a);相应的list使用LinkedList
        }
        Collections.reverse(list);
        return list;
    }
}

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
429. N叉树的层序遍历

解法 迭代

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        LinkedList<Node> queue = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                Node node = queue.poll();
                tmp.add(node.val);
                queue.addAll(node.children);
            }
            list.add(tmp);
        }
        return list;
    }
}

小结

二叉树的层序遍历和锯齿形层次遍历区别不大，锯齿形需要通过当前层数判断是否要逆序这一层的数组，上述两种实现采用在队首加数达到逆序的效果。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。