📚 12.找树左下角的值

💻 代码实现

/**
 * @url https://leetcode.cn/problems/find-bottom-left-tree-value/description/
 */

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function findBottomLeftValue(root: TreeNode | null): number {
  let maxDepth = Number.MIN_SAFE_INTEGER,
    res;
  const dfs = (root: TreeNode | null | undefined, depth) => {
    if (!root) return -1;
    if (!root.left && !root.right) {
      if (maxDepth < depth) {
        maxDepth = depth;
        res = root.val;
        return;
      }
    }
    // 找最左下角的值，所以先遍历左边，然后先判断下手为强
    dfs(root.left, depth + 1);
    dfs(root.right, depth + 1);
  };
  dfs(root, 1);
  return res;
}

// 层序遍历去做，不过会超时
// function findBottomLeftValue(root: TreeNode | null): number {
//     let val  = 0;
//     const stack = []
//     stack.push(root)
//     while(stack.length){
//         let copyStack = stack.concat()
//         console.log(copyStack)
//         for(let i = 0; i < copyStack.length; i++){
//             const top = stack.shift()
//             if(i === 0){
//                 val = top.val
//             }
//             if(top?.left){
//                 stack.push(top.left)
//             }
//             if(top?.right){
//                 stack.push(top.right)
//             }
//         }
//     }
//     return val
// };