二叉树的最大宽度

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    void dfs(TreeNode* root,int level,vector<vector<int>>& tmp)
    {
        if (level > tmp.size()) tmp.push_back({});
        if (!root)
        {
            tmp[level-1].push_back(0);
            return;
        }
        else tmp[level-1].push_back(1);
        dfs(root->left,level+1,tmp);
        dfs(root->right,level+1,tmp);
    }
    
    int func(vector<int>& tmp)
    {
        int left = 0;
        int right = tmp.size()-1;
        while (left < tmp.size() && tmp[left] != 1) left++;
        while (right >=0 && tmp[right] != 1) right--;
        return right - left + 1;
    }
    
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        vector<vector<int>> tmp;
        dfs(root,1,tmp);
        int res = 0;
        for (auto &c : tmp)
        {
            int len = func(c);
            res = max(res,len);
        }
        return res;
    }
};

import java.util.*;

public class Solution {

    public int widthOfBinaryTree (TreeNode root) {
        // BFS
        if (root == null)  return 0;
        int width = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), left = -1, right = -1; // left、right该层最左、右节点下标
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                if (t.val == -1) {  // -1节点顶替空节点
                    queue.offer(new TreeNode(-1));
                    queue.offer(new TreeNode(-1));
                } else {
                    if (left == -1) left = i;
                    else right = i;
                    if (t.left == null) queue.offer(new TreeNode(-1));
                    else queue.offer(t.left);
                    if (t.right == null) queue.offer(new TreeNode(-1));
                    else queue.offer(t.right);
                }
            }
            if (left == -1 && right == -1) break;
            width = Math.max(width, right == -1 ? 1 : right - left + 1);
        }
        return width;
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC204 二叉树的最大宽度
 * @author d3y1
 */
public class Solution {
    private int result = 0;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode root) {
        return solution1(root);
        // return solution2(root);
    }

    /**
     * 迭代: 层序遍历
     * @param root
     * @return
     */
    private int solution1(TreeNode root){
        levelOrder(root);
        return result;
    }

    /**
     * 层序遍历
     * @param root
     */
    private void levelOrder(TreeNode root){
        if(root == null){
            return;
        }

        // 双端队列
        // deque.offer(tNode) -> tNode 不能为 null
        // Deque<TreeNode> deque = new ArrayDeque<>();
        // deque.offer(tNode) -> tNode 可以为 null
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerLast(root);

        int size;
        TreeNode tNode;
        while(!deque.isEmpty()){
            // 去掉该层左边空节点(first端)
            while(!deque.isEmpty() && deque.peekFirst()==null){
                deque.pollFirst();
            }
            // 去掉该层右边空节点(last端)
            while(!deque.isEmpty() && deque.peekLast()==null){
                deque.pollLast();
            }

            // 节点个数即为宽度
            size = deque.size();
            result = Math.max(result, size);

            // 生成下一层
            while(size-- > 0){
                tNode = deque.pollFirst();
                if(tNode != null){
                    deque.offerLast(tNode.left);
                    deque.offerLast(tNode.right);
                }else{
                    deque.offerLast(null);
                    deque.offerLast(null);
                }
            }
        }
    }

    private HashMap<Integer,Integer> leftIdxMap = new HashMap<>();

    /**
     * 递归: 前序遍历
     * @param root
     * @return
     */
    private int solution2(TreeNode root){
        preOrder(root, 1, 1);
        return result;
    }

    /**
     * 前序遍历
     * @param root
     * @param level
     * @param currIdx
     */
    private void preOrder(TreeNode root, int level, int currIdx){
        if(root == null){
            return;
        }

        // key(level)存在-直接取值 key(level)不存在-先put,再取值
        int leftIdx = leftIdxMap.computeIfAbsent(level, value->currIdx);
        result = Math.max(result, currIdx-leftIdx+1);

        preOrder(root.left, level+1, 2*currIdx);
        preOrder(root.right, level+1, 2*currIdx+1);
    }
}

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return False

        q = []
        q.append(root)

        res = 0
        while len(q) != 0:
            left = 0
            right = len(q)
            while q[left] is None:
                left += 1
            while q[right - 1] is None:
                right -= 1
            res = max(res, right - left)

            next_q = []
            have_next = False
            for index in range(len(q)):
                node = q[index]

                if node is None:
                    next_q.append(None)
                    next_q.append(None)
                    continue

                if node.left:
                    have_next = True
                    next_q.append(node.left)
                else:
                    next_q.append(None)

                if node.right:
                    have_next = True
                    next_q.append(node.right)
                else:
                    next_q.append(None)

            if have_next:
                q = next_q
            else:
                q = []

        return res

package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
*/
func widthOfBinaryTree( root *TreeNode ) int {
    if root==nil{
        return 0
    }
    root=label(root,1)
    max:=1
    q:=[]*TreeNode{root}
    for len(q)>0{
        new_q:=[]*TreeNode{}
        for _,qi:=range q{
            if qi.Left!=nil{
                new_q=append(new_q,qi.Left)
            }
            if qi.Right!=nil{
                new_q=append(new_q,qi.Right)
            }
        }
        x:=1
        if len(new_q)>1{
            x=new_q[len(new_q)-1].Val-new_q[0].Val+1
        }
        if x>max{
            max=x
        }
        q=new_q
    }
    return max
}

func label(root *TreeNode,x int)*TreeNode{
    if root==nil{
        return nil
    }
    root.Val=x
    root.Left=label(root.Left,x*2)
    root.Right=label(root.Right,x*2+1)
    return root
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        queue<TreeNode*> que;
        que.push(root);

        vector<int> nums;
        nums.push_back(1);
        while(que.empty()==false)
        {
            int size=que.size();
           int count=0;
            for(int i=0;i<size;i++)
            {
                 TreeNode* node=que.front();
                 que.pop();
                if(node->left!=nullptr)
                 {
                     que.push(node->left);
                    count++;}    
                    if(node->right!=nullptr)
                { 
                    que.push(node->right);
                      count++;
                      }  

            }
            nums.push_back(count);
        }

        int max=nums[0];
        for(int i=0;i<nums.size();i++)
        {
           
            if(nums[i]>max)
            max=nums[i];
        }
return max;
    }
};


做了半天只把每层非空节点的个数计算出来了，用层序遍历的方法，计算每层的个数放入到一个数组中，在数组中找出最大的数即可。

import java.util.*;

public class Solution {
    class IndexTreeNode {
        public Integer val;
        public Integer index;
        public IndexTreeNode left;
        public IndexTreeNode right;

        public IndexTreeNode (TreeNode node, Integer index) {
            this.val = node.val;
            this.index = index;
            this.left = node.left == null ? null : new IndexTreeNode(node.left, 2 * index + 1);
            this.right = node.right == null ? null : new IndexTreeNode(node.right, 2 * index + 2);
        }
    }
    
    public int widthOfBinaryTree (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ans = 1;
        Queue<IndexTreeNode> queue = new LinkedList<>();
        queue.offer(new IndexTreeNode(root, 0));
        while (!queue.isEmpty()) {
            IndexTreeNode head = null;
            IndexTreeNode tail = null;
            for (int s = queue.size(); s > 0; --s) {
                IndexTreeNode n = queue.poll();
                IndexTreeNode[] children = new IndexTreeNode[]{ n.left, n.right };
                for (IndexTreeNode child : children) {
                    if (child != null) {
                        queue.offer(child);
                        if (head == null) {
                            head = child;
                        }
                        tail = child;
                    }
                }
            }
            if (head != null && tail != null) {
                ans = tail.index - head.index + 1;
            }
        }
        return ans;
    }

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        if(!root) return 0;
        queue<pair<TreeNode*,int>> q;
        q.push(make_pair(root, 0));
        int res=0;
        while(!q.empty()){
            int size=q.size();
            int l,r;
            bool flag=true;
            for(int i=0;i<size;++i){
                int index=q.front().second;
                auto p=q.front().first;
                q.pop();
                if(flag){
                    flag=false;
                    l=index;
                    r=index;
                }
                r=index;
                if(p->left) q.push(make_pair(p->left, 2*index+1));
                if(p->right) q.push(make_pair(p->right,2*index+2));
            }
            res=max(res,r-l+1);
        }
        return res;
    }
};

function widthOfBinaryTree( root ) {
    // write code here
 const queue = [[root, 0]];
  let res = 0; // 全局维护最大值
  let left = 0; // 记录当前层最左边节点的计数值
  let right = 0; // 记录当前层最右边节点的计数值
  while (queue.length) {
    left = queue[0][1];
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      let [h, pos] = queue.shift();
      right = pos;
      if (h.left) queue.push([h.left, 2 * (pos - left)]); // 重点，优化掉左边不需要计数的部分
      if (h.right) queue.push([h.right, 2 * (pos - left) + 1]);
    }
    res = Math.max(res, right - left + 1);
  }
  return res;
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        int res = 0;
        queue<pair<TreeNode*,int>> q;
        q.push(make_pair(root,0));
        while(!q.empty()){
            int sz = q.size();
            int l = INT_MAX, r = INT_MIN;
            while(sz--){
                auto t = q.front();
                q.pop();
                TreeNode* temp = t.first;
                int index = t.second;
                l = min(l,index);
                r = max(r,index);
                if(temp->left){
                    q.push(make_pair(temp->left,2 * index + 1));
                }
                if(temp->right){
                    q.push(make_pair(temp->right,2 * index + 2));
                }
            }
            res = max(res, r- l + 1);
        }
         return res;
    }
};

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxWidth = 0;
        while(!queue.isEmpty()){
            TreeNode cur = null;
            int size = queue.size();
            ArrayList<TreeNode> array = new ArrayList<>();
            for(int i = 0; i < size; i++){
                cur = queue.poll();
                array.add(cur);//将每一层的所有节点收集，包括空
                if(cur != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
                    
            }
            int start = 0, end = 0, width = 0;
            //找第一个不为空的
            for(int i = 0; i < array.size(); i++){
                if(array.get(i) != null) {
                    start = i;
                    break;
                }
            }
            //找最后一个不为空的
            for(int i = array.size()-1; i >= 0; i--){
                if(array.get(i) != null) {
                    end = i;
                    break;
                }
            }
            //计算宽度
            //如果某一层全空，也会计算宽度为1，但不影响最终结果正确
            width = end - start + 1;
            //更新宽度
            if(width > maxWidth)
                maxWidth = width;
        }
        return maxWidth;
    }
}最后一个样例过不了，但是我怎么觉得答案有点问题。。。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 遍历的当前节点
        TreeNode currentNode = node;
        // 下一层开始节点
        TreeNode nextStart = null;
        // 下一层结束节点
        TreeNode nextEnd = node;
        // 当前层结束节点
        TreeNode currentEnd = node;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int count = 0;
        int maxCount = 0;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            if (currentNode == null) {
                count++;
                continue;
            }
            if (currentNode.left != null) {
                nextEnd = currentNode.left;
                nextStart = nextStart != null ? nextStart : currentNode.left;
                queue.add(currentNode.left);
            } else {
                if (currentNode.left == null && nextStart != null) {
                    queue.add(currentNode.left);
                }
            }

            if (currentNode.right != null) {
                nextEnd = currentNode.right;
                nextStart = nextStart != null ? nextStart : currentNode.right;
                queue.add(currentNode.right);
            } else {
                if (currentNode.right == null && nextStart != null) {
                    queue.add(currentNode.left);
                }
            }
            count++;
            if (currentEnd == currentNode) {
                nextStart = null;
                currentEnd = nextEnd;
                maxCount = Math.max(count, maxCount);
                count = 0;
            }
        }
        return maxCount;
    }
}