513.找树左下角的值

链接：513.找树左下角的值
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

题解 1 - typescript

• 编辑时间：2021-07-21
• 执行用时：88ms
• 内存消耗：43.2MB
• 编程语言：typescript
• 解法介绍：层序遍历。

function findBottomLeftValue(root: TreeNode): number {
  const queue: TreeNode[] = [root];
  let size = 1;
  let ans = root.val;
  while (queue.length !== 0) {
    const node = queue.shift()!;
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
    if (--size === 0 && queue.length !== 0) {
      ans = queue[0].val;
      size = queue.length;
    }
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2022-06-22
• 执行用时：12ms
• 内存消耗：21.1MB
• 编程语言：cpp
• 解法介绍：层序遍历。

class Solution {
   public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = root->val, size = 1;
        while (q.size()) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            if (--size == 0) {
                size = q.size();
                if (q.size()) ans = q.front()->val;
            }
        }
        return ans;
    }
};