513. 找树左下角的值

第一眼感觉用层序可以很快的找到最下一面层，然后再判断是

确实卡哥也说层序更加的简单

层序遍历

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
int getMaxheight(TreeNode *node) {
    if (node == NULL) return 0;
    return max(getMaxheight(node->left), getMaxheight(node->right)) + 1;
}
int findBottomLeftValue(TreeNode *root) {
    //个人尝试用层序遍历
    //如何判断是最后一层，求最大深度？
    int h = getMaxheight(root);
    int curH = 0;//最开始的时候在第一层，深度也是1
    queue<TreeNode *> q;
    if (root != NULL) q.push(root);
    while (!q.empty()) {
        int size = q.size();
        curH++;
        for (int i = 0; i < size; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (curH == h) return node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    //说了至少有一个节点，所以这里执行不到的
    return 0;
}

卡哥的递归遍历