前言
如何完成二叉树的宽度优先遍历（常见题目：求一颗二叉树的宽度）
二叉树的宽度优先遍历
以下面的二叉树为例：
如果对其进行宽度优先遍历，打印出来的顺序是1,2,3,4,5,6,7
Java版
public static void w(Node head){ if(head == null){ return; } Queue<Node> queue = new LinkedList<>(); queue.add(head); while(!queue.isEmpty()){ Node cur = queue.poll(); System.out.printIn(cur.value); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } } 复制代码
求一颗二叉树的宽度
题目分析
以下面的二叉树为例：
网络异常，图片无法展示
|
这个二叉树的最大宽度是3，位于第三层。
在上述对二叉树的宽度优先遍历的基础上，我们还需要在遍历时知道该节点位于第几层，以便于记录每一层中的节点个数。
public static void w(Node head){ if(head == null){ return; } Queue<Node> queue = new LinkedList<>(); queue.add(head); HashMap<Node, Integer> levelMap = new HashMap<>(); levelMap.put(head, 1); int curLevel = 1; int curLevelNodes = 0; int max = Integer.MIN_VALUE; while(!queue.isEmpty()){ Node cur = queue.poll(); int curNodeLevel = levelMap.get(cur); if(curNodeLevel == curLevel){ curLevelNodes++; }else{ curLevel++; curLevelNodes=1; } max = Math.max(max, curLevelNodes); if(cur.left != null){ levelMap.put(cur.left, curNodeLevel+1); queue.add(cur.left); } if(cur.right != null){ levelMap.put(cur.right, curNodeLevel+1); queue.add(cur.right); } } return max } 复制代码
进阶：Leetcode- 662. 二叉树最大宽度
根据上面的例子，这道题好像也是广度优先遍历的一个例子，在其广度优先遍历的基础上，遍历时知道该节点位于哪一层，并记录该层的节点个数，但是好像，此法不通...因为它中间空的位置也要计算！
难点：两端点之间的null节点也计入长度
此时，我们可以利用完全二叉树的性质：
- 对于一颗完全二插树，如果按照从上至下，从左往右对所有节点从零开始顺序编号
- 则父节点的左孩子节点的序号：2i+1
- 父节点的左孩子节点的序号：2i+2
var widthOfBinaryTree = function(root) { // 首先实现广度优先遍历，在其基础上，遍历时知道该节点位于哪一层，并记录该层的节点个数 // 难点：两端点之间的null节点也计入长度 // const queue = [root]; // while(queue.length){ // const cur = queue.shift(); // console.log(cur.val); // cur.left && queue.push(cur.left); // cur.right && queue.push(cur.right); // } // 如果两端点之间的null节点不计入长度 // const queue = [root]; // const levelMap = new Map(); // let curLevel = 1; // let max = 0; // let curLevelNodes = 0; // levelMap.set(root, 1); // while(queue.length>0){ // const cur = queue.shift(); // const curNodeLevel = levelMap.get(cur); // if(curNodeLevel === curLevel){ // curLevelNodes++; // }else{ // curLevel++; // curLevelNodes = 1; // } // max = Math.max(max, curLevelNodes); // if(cur.left){ // queue.push(cur.left); // levelMap.set(cur.left, curNodeLevel+1); // } // if(cur.right){ // queue.push(cur.right); // levelMap.set(cur.right, curNodeLevel+1) // } // console.log(cur, curNodeLevel, curLevel, curLevelNodes, max) ; // } // return max const max = []; function dfs(node, dep, idx) { if (!node) return; max[dep] = (max[dep] || [idx, idx]); max[dep][0] = Math.min(max[dep][0], idx); max[dep][1] = Math.max(max[dep][1], idx); dfs(node.left, dep + 1, (idx << 1) + 1); dfs(node.right, dep + 1, (idx << 1) + 2); } dfs(root, 0, 0); return max.reduce((max, [l, r]) => Math.max(max, r - l), 0) + 1; };
