513-找树左下角的值

LeetCode 513. Find Bottom Left Tree Value

LeetCode-513

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

Input: root = [2,1,3]
Output: 1

method 1: 递归

需要找到最底层的左边节点，用先序遍历，如果当前深度比记录的深度大，就更新深度和结果值
因为是遍历整棵树，所以不需要返回值

更新深度的时候，该节点肯定是当前深度的第一个节点

int maxDepth = -1;  // 记录最大深度
int ret;
void traversal(TreeNode *root, int depth) {
    if (!root) return;
    if (depth > maxDepth) { // 更新最大深度，一层只更新一次，就是最左边的节点
        maxDepth = depth;
        ret = root->val;
    }
    traversal(root->left, depth + 1);
    traversal(root->right, depth + 1);
}
int findBottomLeftValue(TreeNode* root) {
    traversal(root, 0);
    return ret;
}

---

method 2: 层序遍历

记录每层的第一个节点

int findBottomLeftValue(TreeNode* root) {
    queue<TreeNode*> q;
    if (!root) return 0;
    int res = 0;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode *top = q.front();
            q.pop();
            if (i == 0) res = top->val; // 记录每层第一个节点
            if (top->left) q.push(top->left);
            if (top->right) q.push(top->right);
        }
    }
    return res;
}