[leetcode-二叉树层次遍历并统计每层节点数]--103. Binary Tree Zigzag Level Order Traversal

深碍√TFBOYSˉ_ 2022-07-12 03:42 165阅读 0赞

Question 103. Binary Tree Zigzag Level Order Traversal

> Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
> 
> For example:  
> Given binary tree \[3,9,20,null,null,15,7\],

3
       / \   9  20
        /  \    15   7

return its zigzag level order traversal as:

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

> 二叉树层次遍历 并统计每层节点数。 此外奇数层从左到右输出，偶数层从右到左输出。 和前面的102，107题类似。

给出实现源码：

/** * 二叉树的层次遍历 * 使用队列实现 * @param root * @return */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//队列里面存放结点
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int flag=1;
        //如果为空树就直接返回
        if(root == null){
            return result;
        }
    
        queue.offer(root);//根节点先入队
        //只要队列非空就一直循环;
        while (!queue.isEmpty()){
            int levelNum = queue.size();//获取当前层的节点数.
            flag++;
    
            //从右到左遍历时才使用
            Stack<Integer> stack = new Stack<>();
    
            List<Integer> subList = new ArrayList<>();
            //遍历当前层结点
            for(int i=0; i<levelNum; i++){
                //队首出队并将value加入子list
                TreeNode node = queue.poll();
                //偶数行就用栈存储
                if(flag %2 == 1) {
                    stack.push(node.val);
                }else{
                    subList.add(node.val);
                }
    
                //将非空左右子树加入queue
                if(node.left != null){
       //如果队首的左结点不为空就把左结点入队
                    queue.offer(node.left);
                }
                if(node.right != null){
       //如果队首的右结点不为空就把右结点入队
                    queue.offer(node.right);
                }
            }
            //偶数行就从栈中取数据.
            if(flag %2 == 1) {
                while (!stack.isEmpty()){
                    subList.add(stack.pop());
                }
                result.add(subList);
            }else {
                result.add(subList);//添加一层
            }
        }
        return result;
    }

测试用例和前面一样，现在只给出测试用例输出：

3, 
    20, 9, 
    15, 7,

满足要求。

本文完整代码的github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question103.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question103.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question103.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question103.java