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

偏执的太偏执、 2023-07-21 08:50 24阅读 0赞

## 662. 二叉树最大宽度 ##

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

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

示例 1:

输入:

1
         /   \
        3     2
       / \     \  
      5   3     9

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

输入:

1
         /  
        3    
       / \       
      5   3

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

输入:

1
         / \
        3   2 
       /        
      5

输出: 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就是我右面的点，每一次进去，只要比最左面大，就保存  
右面的点–左面的点=我这一层的大小  
左面的就是val*2-1，我如果有左面的就是我每一层会乘2，然后左面就是减去1  
右面的就是val*2；  
自己带一个树试试就明白了，我当时也想了半天才明白

/** * 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;
            
        }
    }