二叉树的最大宽度

给定一个二叉树，请你求出此二叉树的最大宽度。

本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。

方法一：广度搜索

具体方法

给每个节点设置一个索引index，如果向左走，就将$2\ast index2*index$左子树存起来，如果向右走，就将$2\ast index+12\; *\; index\; +\; 1$，当在同一层深度时$leftleft$和$rightright$，宽度为$right-left+1right-\; left\; +\; 1$。

代码实现

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */

    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null)
            return 0;
        Queue<AnnotatedNode> queue = new LinkedList();
        //根节点入队
        queue.add(new AnnotatedNode(root, 0, 0));
        int max =0;
        int curDepth = 0, left = 0, ans = 0;
        //广搜
        while(!queue.isEmpty()){
            AnnotatedNode a = queue.poll();
            if(a.node!=null){
                //左右节点入队
                queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
                queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
                if (curDepth != a.depth) {
                    curDepth = a.depth;
                    left = a.pos;
                
            }
              // 更新最大宽度
            max = Math.max(max, a.pos - left + 1);
            }

        }
        return max;
    }
}

class AnnotatedNode {
    TreeNode node;
    int depth, pos;
    AnnotatedNode(TreeNode n, int d, int p) {
        node = n;
        depth = d;
        pos = p;
    }
}

复杂度分析

• 时间复杂度： $O(n)O(n)$，其中 $nn$ 是输入树的节点数目，我们遍历每个节点一遍。
• 空间复杂度：$O(n)O(n)$，这是 $queuequeue$ 的大小。

方法二：深度搜索

具体方法

按照深度优先的顺序，记录每个节点的$indexindex$。对于每一个深度，第一个到达的位置会被记录在 $left[depth]left[depth]$中。

然后对于每一个节点，它对应这一层的可能宽度是$index-left[depth]+1index\; -\; left[depth]\; +\; 1$ 。我们将每一层这些可能的宽度去一个最大值就是答案。

代码实现

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
        int res;
    Map<Integer, Integer> left;
    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        res = 0;
        left = new HashMap();
        dfs(root, 0, 0);
        return res;
    }
      public void dfs(TreeNode root, int depth, int index) {
        if (root == null) return;
        left.computeIfAbsent(depth, x-> index);
        res = Math.max(res, index - left.get(depth) + 1);
          //遍历左子树 
        dfs(root.left, depth + 1, 2 * index);
          //遍历右子树 
        dfs(root.right, depth + 1, 2 * index + 1);
    }

}

复杂度分析

• 时间复杂度： $O(n)O(n)$，其中 n 是树中节点的数目，我们需要遍历每个节点。
• 空间复杂度：$O(n)O(n)$ ，这部分空间是因为我们 DFS 递归过程中有 n 层的栈。