二叉树的宽度-在线编程-K6K4.com

二叉树某一层的宽度指的是该层中节点的个数。而二叉树的宽度是指所有层中宽度的最大值。
注：若二叉树为空，则返回0。

输入、输出描述

输入：

给定一个二叉树的根节点

输出：

二叉树的宽度

Example

输入：

二叉树如下：
    1
   / \
   2  3
  /  / \
  4  5  6
   \
    7

输出：

代码：

import java.util.*;

public class Main {

    /**
    //该段代码仅用于调试，提交时请注释该段代码
    class TreeNode<T> {

        public T data;

        public TreeNode<T> left;

        public TreeNode<T> right;
    }
 */ 
  public int solution(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }

        List<TreeNode> list1 = new ArrayList<>();
        List<TreeNode> list2 = new ArrayList<>();
        list1.add(root);

        int maxWidth = 0;

        while (!list1.isEmpty() || !list2.isEmpty()) {
            if (!list1.isEmpty()) {
                int size = list1.size();
                if (size > maxWidth) {
                    maxWidth = size;
                }

                for (int i = 0; i < size; i++) {
                    TreeNode node = list1.get(i);
                    if (node.left != null) {
                        list2.add(node.left);
                    }
                    if (node.right != null) {
                        list2.add(node.right);
                    }
                }

                list1.clear();
            } else {
                int size = list2.size();
                if (size > maxWidth) {
                    maxWidth = size;
                }

                for (int i = 0; i < size; i++) {
                    TreeNode node = list2.get(i);
                    if (node.left != null) {
                        list1.add(node.left);
                    }
                    if (node.right != null) {
                        list1.add(node.right);
                    }
                }

                list2.clear();
            }

        }

        return maxWidth;

    }
}