Topic describes
Answer key
Remember the binary tree sequence traversal blog.csdn.net/fisherish/a… If the node is I, the left child is I *2 and the right child is I *2 + 1. And we can do it in this case.
In Leetcode 440. Lexicographical KTH smallest number, we determine the number of nodes in a layer by subtracting the leftmost node value from the rightmost node value (if sorted). So we can make up our own data by counting the nodes at each level from 0 and assigning them a value of 0, the second node at each level assigning a value of 1, and so on. Let’s take the rightmost node minus the leftmost node plus 1, and that’s the number of nodes at this level.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int res = 0; public int widthOfBinaryTree(TreeNode root) { Deque<TreeNode> q = new ArrayDeque<>(); root.val = 0; q.offer(root); while (! q.isEmpty()) { int size = q.size(); res = Math.max(res, q.getLast().val - q.getFirst().val + 1); while (size > 0) { TreeNode node = q.poll(); System.out.println(node.val); size--; if (node.left ! = null) { node.left.val = node.val * 2; q.offer(node.left); } if (node.right ! = null) { node.right.val = node.val * 2 + 1; q.offer(node.right); } } } return res; }}Copy the code