Maximum Width of Binary Tree

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/maximum-width-of-binary-tree/description/

想法

初看应该还是比较简单的吧，记录下头在哪，尾在哪应该就可以了吧

啊，没那么简单！！！
不能简单的一直向边上走
看来很遍历一下来设置了

答案

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> l, r;
    void travel(int level, int index, TreeNode* root) {
        if (!root)
            return;
        if (l.size() == level) {
            l.push_back(index);
            r.push_back(index);
        } else {
            if (index > r[level]) {
                r[level] = index;
            }
        }
        travel(level + 1, 2 * index - 1, root->left);
        travel(level + 1, 2 * index, root->right);
    }
    int widthOfBinaryTree(TreeNode* root) {
        
        if (!root)
            return 0;
        travel(0, 1, root);
        
        int max = 0;
        for (int i = 0; i < l.size(); i++) {
            if (r[i] - l[i] + 1 > max)
                max = r[i] - l[i] + 1;
        }
        return max;
    }
};

回顾

一开始想的有点简单了，不过后来也只是需要稍微改变下思路

LeetCode相比于CodeWars可能整体难度的确有点小，可能自己也进步了，好多medium的题目原来做起来很费劲，现在比较轻松了，great！