662. Maximum Width of Binary Tree

LeetCode


  1. Maximum Width of Binary Tree:题目链接

BFS

基本思想：其实就是求二叉树上所有层里 从第一层到最后一层，所在层的宽度 = 最右结点的位置-最左结点的位置 + 1,求所有层中宽度最大的值，利用层次遍历的思想，父亲结点编号idx = i，那么左孩子编号idx = 2i，右孩子编号idx = 2i + 1， 定义一个leftIdx变量每次指向当前深度的最左结点的位置 

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
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {

     private class nodeIndex{
         TreeNode node;
         int idx;
         nodeIndex(TreeNode node, int idx){
            this.node = node;
            this.idx = idx;
         }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<nodeIndex> queue = new LinkedList<>();
        queue.offer(new nodeIndex(root, 0));
        int res = 0; 
        int depth = 0, size = 0;
        while (queue.size() != 0) {
            depth++;  // 当前深度
            int left = queue.peek().idx; // 当前深度的第一个节点的idx
            size = queue.size(); // 第depth层所有节点个数(不含NULL)
            
            for (int i = 0; i< size ; ++i) {  // 遍历该depth层的节点 
                nodeIndex  front = queue.peek();
                queue.poll();
                if (front.node.left != null) { 
                    queue.offer(new nodeIndex(front.node.left, front.idx * 2));
                }
                if (front.node.right != null) { 
                    queue.offer(new nodeIndex(front.node.right, front.idx * 2+1));
                }
                if (i == size -1) { // 当遍历到当前depth的最后一个节点  更新res
                    res = res < (front.idx - left + 1) ? (front.idx - left + 1) : res;
                }
            }
        }
        return res;
    }
}

本文标题:662. Maximum Width of Binary Tree

文章作者:XerDemo

发布时间:2019-02-11, 08:07:32

最后更新:2019-03-11, 17:17:29

原始链接:https://xerdemo.github.io/2019/02/11/662-Maximum-Width-of-Binary-Tree/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. BFS
|