662. 二叉树最大宽度(中等)

1，问题描述

662. 二叉树最大宽度

难度：中等

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

示例 3：

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示：

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

2，初步思考

​ 最初的思考中想到了，空间换时间的解法，本质是一个非规范的深度优先搜索算法解题widthOfBinaryTree

​ 看了官方的答案后，又写出了标准的bfs、dfs解法

3，代码处理

第一次的思路想复杂了

import support.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _662二叉树最大宽度 {

    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K left, V right) {
            this.key = left;
            this.value = right;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

    public int widthOfBinaryTree_gov_bfs(TreeNode root) {
        int res = 1;
        List<Pair<TreeNode, Integer>> arr = new ArrayList<Pair<TreeNode, Integer>>();
        arr.add(new Pair<TreeNode, Integer>(root, 1));
        while (!arr.isEmpty()) {
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<Pair<TreeNode, Integer>>();
            for (Pair<TreeNode, Integer> pair : arr) {
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
                }
            }
            res = Math.max(res, arr.get(arr.size() - 1).getValue() - arr.get(0).getValue() + 1);
            arr = tmp;
        }
        return res;
    }

    public int widthOfBinaryTree_bfs(TreeNode root) {
        List<Pair<TreeNode, Integer>> levelPre = new ArrayList<Pair<TreeNode, Integer>>();
        levelPre.add(new Pair<TreeNode, Integer>(root, 1));
        List<Pair<TreeNode, Integer>> levelNext = new ArrayList<Pair<TreeNode, Integer>>();
        int max = 1;

        while (!levelPre.isEmpty()) {
            Pair<TreeNode, Integer> pair = levelPre.get(0);
            TreeNode node = pair.getKey();
            Integer index = pair.getValue();
            if (node.left != null) {
                levelNext.add(new Pair<TreeNode, Integer>(node.left, index * 2));
            }
            if (node.right != null) {
                levelNext.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
            }
            levelPre.remove(0);
            if (levelPre.isEmpty()) {
                if (!levelNext.isEmpty()) {
                    int len = levelNext.get(levelNext.size() - 1).getValue() - levelNext.get(0).getValue() + 1;
                    max = Math.max(max, len);
                    levelPre = levelNext;
                    levelNext = new ArrayList<>();
                }
            }
        }
        return max;
    }

    Map<Integer, Integer> levelMin = new HashMap<Integer, Integer>();

    public int widthOfBinaryTree_gov_dfs(TreeNode root) {
        return dfs(root, 1, 1);
    }

    public int dfs(TreeNode node, int depth, int index) {
        if (node == null) {
            return 0;
        }
        levelMin.putIfAbsent(depth, index); // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值(如果已经有了就直接忽略即可)
        return Math.max(index - levelMin.get(depth) + 1, Math.max(dfs(node.left, depth + 1, index * 2), dfs(node.right, depth + 1, index * 2 + 1)));
    }


    public int widthOfBinaryTree_dfs(TreeNode root) {
        return dfs2(root, 0, 0);// 深度
    }

    private Integer dfs2(TreeNode root, Integer depth, Integer index) {
        if (root == null) return 0;
        levelMin.putIfAbsent(depth, index);
        return Math.max(index - levelMin.get(depth) + 1,
                Math.max(dfs2(root.left, depth + 1, index * 2), dfs2(root.right, depth + 1, index * 2 + 1)));
    }


    // 没有空间要求，可以直接用一个链表的数组存储相关的数据，之后再进行计算。（不是最好的，其实没有必要使用空间存储）
    public int widthOfBinaryTree(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, root, 0, 0);
        int max = 0;
        for (List<Integer> re : res) {
            int len = re.getLast() - re.getFirst() + 1;
            max = Math.max(max, len);
        }
        return max;
    }


    private void dfs(List<List<Integer>> res, TreeNode root, int depth, int index) {
        if (root == null) return;
        List<Integer> indexList;
        if (res.size() <= depth) {
            indexList = new ArrayList<>();
            res.add(indexList);
        } else {
            indexList = res.get(depth);
        }
        indexList.add(index);

        index = index * 2;
        depth = depth + 1;

        dfs(res, root.left, depth, index);
        dfs(res, root.right, depth, index + 1);
    }

    public static void main(String[] args) {
        _662二叉树最大宽度 binaryTreeMaxWidth = new _662二叉树最大宽度();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);

        System.out.println(binaryTreeMaxWidth.widthOfBinaryTree(root));
    }
}

/**
 * 0
 * 1,2
 * 3,4,5,6
 * <p>
 * 0
 * 0,1
 * 0,1,2,3
 * 0,1,2,3,4,5,6,7
 * num*2+?1
 */

​ 官方题解中速度最快的解法，本质与stack栈一致

class Solution {
    public boolean isValid(String s) {
        char[] s1 = s.toCharArray();
        int[] ss = new int[s.length()];
        int top = -1,n = s.length();
        for(int i = 0;i < n;i ++){
            if(s1[i] == '(' || s1[i] == '{' || s1[i] == '['){
                ss[++ top] = s1[i];
            }
            else{
                if(s1[i] == ')'){
                    if(top == -1 || ss[top] != '(')
                        return false;
                    top --;
                }
                else if(s1[i] == '}'){
                    if(top == -1 || ss[top] != '{')
                        return false;
                    top --;
                }
                else if(s1[i] == ']'){
                    if(top == -1 || ss[top] != '[')
                        return false;
                    top --;
                }
            }
        }
        return top == -1;
    }
}

4，扩展知识

4.1，广度优先搜索

（Breadth-First Search，BFS）算法是一种用于图或树结构的遍历算法，以下是关于它的详细介绍：

算法原理

• 从起始节点开始，首先访问起始节点，然后将其所有未访问过的邻居节点加入到一个队列中。接着，从队列中取出第一个节点，访问它并将其未访问的邻居节点加入队列，如此循环，直到队列为空或者找到目标节点。该算法按照层次顺序进行搜索，先访问距离起始节点近的节点，再逐步扩展到距离更远的节点，就像在一层一层地向外扩展搜索范围。

4.2，深度优先搜索

​ （Depth-First Search，简称 DFS）算法是一种用于遍历或搜索图、树等数据结构的算法，以下是关于它的详细介绍：

算法思想

• 从起始节点开始，沿着一条路径尽可能深地探索，直到无法继续或者达到目标节点，然后回溯到前一个节点，继续探索其他路径，直到遍历完所有可达节点或找到目标。可以想象成在一个迷宫中，尽可能地往深处走，走到死胡同后再退回来，尝试其他未走过的路。