如何做电影网站不违法,湘潭网站开发公司,成都企业建站模板,瑞安做网站建设哪家好二叉树最大宽度
https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
1、考虑树的宽度一定是在一层上的所以进行BFS#xff0c;树的BFS不建议直接使用队列#xff0c;每次add/offer然后poll/remove#xff0c;这样子层级关系不好显示。我们可以定义…二叉树最大宽度
https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
1、考虑树的宽度一定是在一层上的所以进行BFS树的BFS不建议直接使用队列每次add/offer然后poll/remove这样子层级关系不好显示。我们可以定义两个数组每次从List里面取出所有的元素这些元素就是一层上的所有的节点。然后进行遍历将子节点插入到另外一个数组这样子会非常清晰。 2、那如何计算宽度我们考虑利用数组建树的思想。比如[1,2,3]可以构成一颗二叉树1是根节点2和3是孩子二者的下标分别是×2和×21这样子不同的节点就有了自己的编号。而两个节点的距离就是下标差。最大的宽度不就是每一个List最后一个元素和第一个元素的下标差的最大值嘛。遍历每一层取最大即可 扩展字节面试题Z字形遍历树利用上面的思想非常简单只需要一个变量每多一层判断奇数还是偶数对List正着或者倒着遍历。
class Solution {//主要还是考虑API的使用public int widthOfBinaryTree(TreeNode root) {//思路BFS加一个变量同时记录下来两个节点的数据差然后就可以直接做差得到宽度了//由于要一层一层的取所以拿list更加方便ListPairTreeNode, Integer list new ArrayList();int ans 0;list.add(new PairTreeNode, Integer(root,1));while(!list.isEmpty()){ListPairTreeNode, Integer temp new ArrayList();for(int i0;ilist.size();i){PairTreeNode, Integer p list.get(i);TreeNode t p.getKey();Integer index p.getValue();TreeNode left t.left;TreeNode right t.right;if(left!null) temp.add(new PairTreeNode, Integer(left,index*2));if(right!null) temp.add(new PairTreeNode, Integer(right,index*21));ans Math.max(ans,(i0?1:1index-list.get(0).getValue()));}list temp;}return ans;}
}
