参考题解
层序遍历,给节点的值编号,给每个节点一个 position 值,如果我们走向左子树,那么 position -> position * 2,如果我们走向右子树,那么 position -> positon * 2 + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Solution { public int widthOfBinaryTree(TreeNode root) { if (root == null) { return 0;} int maxWidth = 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); root.val = 0; while (!queue.isEmpty()) { int curWidth = queue.getLast().val - queue.getFirst().val + 1; for (int i = queue.size(); i > 0 ; --i) { TreeNode cur; cur = queue.poll(); if (cur.left != null) { queue.add(cur.left); cur.left.val = cur.val*2; } if (cur.right != null) { queue.add(cur.right); cur.right.val = cur.val*2 + 1; } } if (curWidth > maxWidth) { maxWidth = curWidth; } } return maxWidth; } }
|