Java实现 LeetCode 662 二叉树最大宽度(递归)

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就是我右面的点,每一次进去,只要比最左面大,就保存
右面的点–左面的点=我这一层的大小
左面的就是val2-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;

}
}


作者:南 墙

相关推荐

使用VSCode开发和调试.NET Core程序的方法

使用VSCode开发和调试.NET Core程序的方法

vscode写python时的代码错误提醒和自动格式化的方法

VSCode写vue项目一键生成.vue模版,修改定义其他模板的方法

Vue项目vscode 安装eslint插件的方法(代码自动修复)

Vue项目vscode 安装eslint插件的方法(代码自动修复)