Java实现 LeetCode 662 二叉树最大宽度（递归）

662. 二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入:

       1

     /   \

    3     2

   / \     \

  5   3     9

输出: 4

解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入:

输出: 2

解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入:

输出: 2

解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入:

      1

     / \

    3   2

   /     \

  5       9

 /         \

6           7

输出: 8

解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

PS：

min就是我这一层最左面的点

max就是我右面的点，每一次进去，只要比最左面大，就保存

右面的点–左面的点=我这一层的大小

左面的就是val2-1，我如果有左面的就是我每一层会乘2，然后左面就是减去1

右面的就是val2；

自己带一个树试试就明白了，我当时也想了半天才明白

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

     class Node {

        int min, max;

        Node next;

    }

    private void calNode(TreeNode node, int val, Node level ){

        if (level.min==0) {

            level.min=val;

            level.max=val;

        } else if (val>level.max) {

            level.max=val;

        }

        if (node.left==null && node.right==null) return;

        if (level.next==null) level.next = new Node();

        if (node.left!=null) calNode(node.left, val*2-1, level.next);

        if (node.right!=null) calNode(node.right, val*2, level.next);

    }

    public int widthOfBinaryTree(TreeNode root) {

        if (root==null) return 0;

        Node level = new Node();

        calNode(root, 1, level);

        int k, res=0;

        while (level!=null){

            k = level.max - level.min + 1;

            if (k>res) res = k;

            level = level.next;

        }

        return res;

    }

}

巴特西

Java实现 LeetCode 662 二叉树最大宽度（递归）

662. 二叉树最大宽度

最新文章

热门文章