【Day 16 】2023-03-01 - 513. 找树左下角的值

[azl397985856]

513. 找树左下角的值

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

前置知识

暂无

题目描述

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1
 

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7
 

[Manwzy]

/**

• Definition for a binary tree node.
• function TreeNode(val, left, right) {
• this.val = (val===undefined ? 0 : val)
• this.left = (left===undefined ? null : left)
• this.right = (right===undefined ? null : right)
• } */ /**
• @param {TreeNode} root
• @return {number} */

var traves = (node,depth)=>{ if(!node){ return null } const left = traves(node.left,depth+1) const right = traves(node.right,depth+1) if(!left && !right){ node.depth = depth } else if(!right || (left && left.depth >= right.depth)){ node.depth = left.depth node.val = left.val } else { node.depth = right.depth node.val = right.val }

return node } var findBottomLeftValue = function(root) { return traves(root,0).val };

[Elsa-zhang]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return None

        sequene = []
        sequene.append(root)

        while sequene:
            lenghth = len(sequene)
            num = sequene[0].val

            for i in range(lenghth):
                node = sequene.pop(0)
                left, right = node.left, node.right

                if left:
                    sequene.append(left)
                if right:
                    sequene.append(right)
        return num

[JiangyanLiNEU]

• BFS
• T = O(N) N is the number of the nodes in the tree
• S = O(N) N is the greatest number of the nodes in one layer

  class Solution:
  def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
      trees = [root]
      leftMost = None
      while trees:
          leftMost = trees[0].val
          temp = []
          for tree in trees:
              if tree.left:
                  temp.append(tree.left)
              if tree.right:
                  temp.append(tree.right)
          trees = temp
      return leftMost

[Yufanzh]

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        # what's the best way to keep track of the layer depth? --> BFS, as the queue record the leftmost value in the head of the queue
        queue = collections.deque()
        queue.append(root)
        while queue:
            nlen = len(queue)
            ans = queue[0].val
            for i in range(nlen):
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return ans

[yfu6]

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:

        tree = [root]
        ans = 0
        while tree:
            nx = []
            for node in tree:
                if node.left:
                    nx.append(node.left)
                if node.right:
                    nx.append(node.right)
            if not nx:
                ans = tree[0].val
                break
            tree = nx
        return ans

[Abby-xu]

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        res = []
        self.dfs(root, res, 0)
        return res[-1][0]

    def dfs(self, root, res, level):
        if not root: return
        if level == len(res): res.append([])
        res[level].append(root.val)
        self.dfs(root.left, res, level + 1)
        self.dfs(root.right, res, level + 1)

[NorthSeacoder]

BFS

var findBottomLeftValue = function(root) {
    //层序遍历
    const queue = [root];
    let res;
    while (queue.length) {
        const cur = queue.shift();
        //先循环右节点,保证最后的是左节点
        if (cur.right) queue.push(cur.right);
        if (cur.left) queue.push(cur.left);
        res = cur.val;
    }
    return res;
};

• TC:O(n)

• SC:O(n)

  DFS

  var findBottomLeftValue = function(root) {
  let res;
  let curHeight = -1;
  const dfs = (node, height) => {
      if (!node) return node;
     //先序/中序/后序都可以,只要保证先遍历的是左节点
      if (height > curHeight) {
          curHeight = height;
          res = node.val;
      }
      dfs(node.left, height + 1);
      dfs(node.right, height + 1);
  };
  
  dfs(root, 0);
  return res;
  };

• TC:O(n)
• SC:O(n)

[Hughlin07]

class Solution {

int maxLevel = 0;
Map<Integer, Integer> map = new HashMap<>();
public int findBottomLeftValue(TreeNode root) {
    // if(root == null) return 0;
    dfs(root, 0);
    return map.get(maxLevel);
}

public void dfs(TreeNode root, int level){
    if(root==null)return;
    int newLevel = level +1;
    dfs(root.left, newLevel);
    if(newLevel > maxLevel && !map.containsKey(newLevel)){
        map.put(newLevel, root.val);
        maxLevel = newLevel;
    }
    dfs(root.right, newLevel);
}

}

Time Complexity: O(N)

Space Complexity: O(h), h is the height of the tree

[954545647]

思路

两种思路：递归 和 BFS

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

var findBottomLeftValue = function (root) {
  if (!root) return root;
  let arr = [root];
  let res = root;
  while (arr.length) {
    let cur = arr.shift();
    if (cur.right) arr.push(cur.right);
    if (cur.left) arr.push(cur.left);
    if (cur.left) {
      res = cur.left;
    } else if (cur.right) {
      res = cur.right;
    }
  }
  return res.val;
};

[bookyue]

TC: O(n)
SC: O(1)

    private int ans;
    private int max;

    public int findBottomLeftValue(TreeNode root) {
        ans = 0;
        max = 0;
        dfs(root, 1);
        return ans;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) return;

        if (depth > max) {
            max = depth;
            ans = root.val;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }

[tzuikuo]

思路

递归

代码

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> curq,lastq;
        if(!root) return 0;
        curq.push(root);
        while(!curq.empty()){
            TreeNode* left=curq.front();
            while(!curq.empty()){
                TreeNode* temp=curq.front();
                if(temp->left) lastq.push(temp->left);
                if(temp->right) lastq.push(temp->right);
                curq.pop();
            }
            if(lastq.empty()) return left->val;
            while(!lastq.empty()){
                TreeNode* temp2=lastq.front();
                curq.push(temp2);
                lastq.pop();
            }
        }
        return 0;
    }
};

复杂度分析 待定

[airwalkers]

// 思路：中序遍历，比较当前高度与记录的最高高度，如果当前高度更高，说明是第一次进入下一层，也就是那一层的最左节点

class Solution {
    int maxHeight = 0, res = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return res;
    }

    // 前序遍历
    private void dfs(TreeNode root, int height) {
        if (height > maxHeight) {
            res = root.val;
            maxHeight = height;
        }

        if (root.left != null) {
            dfs(root.left, height + 1);
        }

        if (root.right != null) {
            dfs(root.right, height + 1);
        }
    }
}

[chanceyliu]

代码

export 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 curVal = 0;
  const dfs = (root: TreeNode | null, height: number) => {
    if (!root) {
      return;
    }
    height++;
    dfs(root.left, height);
    dfs(root.right, height);
    if (height > curHeight) {
      curHeight = height;
      curVal = root.val;
    }
  };

  let curHeight = 0;
  dfs(root, 0);
  return curVal;
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[zzhilin]

思路

• bfs using queue to traverse tree level by level
• when enqueuing, we will make sure to enqueue right childs first to make sure the last node in queue is the leftmost child

代码

from collections import deque
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque()
        q.append(root)
        res = 0

        # level order bfs from right to left
        while q:
            node = q.popleft()
            res = node.val
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)

        return res

复杂度分析 Time: O(N) number of nodes in tree Space: O(w) w is the maximum width of the binary tree, aka max size of queue (one level in binary tree)

[jackgaoyuan]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type BottomLeftInfo struct {
    Level int
    Node *TreeNode
}

func findBottomLeftValue(root *TreeNode) int {
    bottomLeftInfo := BottomLeftInfo{}
    dfs(root, 1, &bottomLeftInfo)
    return bottomLeftInfo.Node.Val
}

func dfs(node *TreeNode, level int,bottomLeftInfo *BottomLeftInfo) {
    if level > bottomLeftInfo.Level {
        bottomLeftInfo.Node = node
        bottomLeftInfo.Level = level
    }
    if node.Left != nil {
        dfs(node.Left, level+1, bottomLeftInfo)
    }
    if node.Right != nil {
        dfs(node.Right, level+1, bottomLeftInfo)
    }
}

[csthaha]

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(h)

代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    //层次遍历 二维数组最后一个的第一个元素。
    if(!root) return root;
    const res = [];
    let queue = [root];
    while(queue.length > 0) {
        let temp = [];
        let values = [];
        for(let item of queue) {
            values.push(item.val);
            if(item.left) {
                temp.push(item.left);
            }
            if(item.right) {
                temp.push(item.right)
            }
        }
        res.push(values);
        queue = temp;
    }
    return res[res.length - 1][0]
};

[FireHaoSky]

思路：

""" 采用广度优先搜索，先存右节点，再存左节点，可以保证最后出现的是左节点 """

解题：python

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
            ans = node.val
        return ans

复杂度分析：

""" 时间复杂度：O(n) 空间复杂度:O(n) """

[FlipN9]

/**
    Approach 1:
    DFS: 先左后右
        记录遍历到的节点的 height 和 这个 height 最左边节点的值
        如果 height 大于 curHeight, curVal = 当前节点的值, curHeight = height
    TC: O(n), SC: O(h)
*/
class Solution1 {
    int curVal, curHeight;

    public int findBottomLeftValue(TreeNode root) {
        curVal = 0;
        curHeight = 0;
        dfs(root, 0);
        return curVal;
    }

    public void dfs(TreeNode root, int height) {
        if (root == null) return;
        height++;
        if (height > curHeight) {
            curHeight = height;
            curVal = root.val;
        }
        dfs(root.left, height);
        dfs(root.right, height);
    }
}

[Ryanbaiyansong]

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        # last row, left most
        q = deque([root])
        ans = 0
        while q:
            sz = len(q)
            level = []
            for _ in range(sz):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)

                if node.right:
                    q.append(node.right)
            ans = level[0]
            level = []

        return ans      

[jiujingxukong]

解题思路

树的搜索。根据题目描述，找到最后一行的最左边的节点值。根据leetcode的题目也可以看出来，findBottomLeftValue。
最直接的方法是用BFS，还可以用DFS。

代码

方法一 BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
function findBottomLeftValue(root) {
  let curLevel = [root];
  while (curLevel.length) {
    let nextLevel = [];
    for (let i = 0; i < curLevel.length; i++) {
      let node = curLevel[i];
      node.left && nextLevel.push(node.left);
      node.right && nextLevel.push(node.right);
    }
    if (!nextLevel.length) {
      return curLevel[0].val;
    }
    curLevel = nextLevel;
  }

  return curLevel[0].val;
}

方法二 DFS

先序遍历 root，维护一个最大深度的变量，记录每个节点的深度，如果当前节点深度比最大深度要大，则更新最大深度和结果项。要记录和更新最大深度和结果项。
树的最后一行找到最左边的值，转化一下就是找第一个出现的深度最大的节点，这里用先序遍历去做，其实中序遍历也可以，只需要保证左节点在右节点前被处理即可。

function findBottomLeftValue(root) {
  let maxDepth = 0;
  let res = root.val;
  dfs(root.left, 0);
  dfs(root.right, 0);
  return res;

  function dfs(cur, depth) {
    if (!cur) return;
    let curDepth = depth + 1;
    if (curDepth > maxDepth) {
      maxDepth = curDepth;
      res = cur.val;
    }
    dfs(cur.left, curDepth);
    dfs(cur.right, curDepth);
  }
}

复杂度分析

方法一 BFS

时间复杂度：O（N）,其中 N 为树的节点总数。 空间复杂度：O（Q）,其中 Q 为队列长度，最坏的情况是满二叉树，此时和 N 同阶，其中 N 为树的节点总数。

方法二 DFS

时间复杂度：O（N）,其中 N 为树的节点总数。 空间复杂度：O（h）,其中 其中 h 为树的高度。

[kyo-tom]

思路

要找出最底层的最左边的节点的值。 分两步考虑：

1. 找出最底下一层（使用 BFS）
2. 找出最左边的节点（每层从右往左遍历，自然每层的最后一个节点就是每层最左边的节点）

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int val = root.val;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            val = node.val;
        }
        return val;
    }
}

复杂度分析

• 时间复杂度：O(n), n 为树的总结点数
• 空间复杂度：O(q)，q 为每一层的节点树，最差最节点数最多的那层的值

[wangqianqian202301]

思路

使用一个队列，从右到左遍历二叉树， 同时设置最左边结点

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return None
        l = []
        bottomLeft = root
        l.append(root)
        while l:
            temp = l.pop(0)
            if temp.right:
                l.append(temp.right)
                bottomLeft = temp.right
            if temp.left:
                l.append(temp.left)
                bottomLeft = temp.left
        return bottomLeft.val

复杂度

O(n) O(n)

[zcytm3000]

class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: curVal = curHeight = 0 def dfs(node: Optional[TreeNode], height: int) -> None: if node is None: return height += 1 dfs(node.left, height) dfs(node.right, height) nonlocal curVal, curHeight if height > curHeight: curHeight = height curVal = node.val dfs(root, 0) return curVal

[Zoeyzyzyzy]

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

class Solution {
    // recursion: if we do preorder traverse, when we arrive at the max depth, 
    // we only need to care the first value we meet.
    // Time Complexity: O(n), Space Complexity: O(n)

    int res = 0;
    int maxDepth = 0;

    public int findBottomLeftValue(TreeNode root) {
        maxDepth(root, 1);
        return res;
    }

    private void maxDepth(TreeNode root, int depth) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                res = root.val;
            }
        }
        maxDepth(root.left, depth + 1);
        maxDepth(root.right, depth + 1);
    }

    //BFS：level of traversal, instead of read from left to right, we can read from right to left,
    //thus, the last element should be the leftmost value in the last row.
    //Time Complexity: O(n), Space Complexity: O(n);
    public int findBottomLeftValue1(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        LinkedList<TreeNode> queue = new LinkedList<>();
        int res = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode curr = queue.poll();
                if (curr.right != null) {
                    res = curr.right.val;
                    queue.offer(curr.right);
                }
                if (curr.left != null) {
                    res = curr.left.val;
                    queue.offer(curr.left);
                }
            }
        }
        return res;
    }

}

[chocolate-emperor]

class Solution {
public:
    //bfs 层次遍历，每层从右往左入队列，队列里最后一个节点即位 最后一层最左节点
    int findBottomLeftValue(TreeNode* root) {
        if(!root->left && !root->right) return root->val;
        TreeNode* last;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            int l = q.size();
            for(int i = 0; i<l;i++){
                TreeNode* tmp = q.front();
                q.pop();
                last = tmp;
                if(tmp->right)   q.push(tmp->right);
                if(tmp->left)   q.push(tmp->left);
            }
        }
        return last->val;
    }
};

[jmaStella]

思路

把depth当作parameter传下去，比较左边和右边的depth，depth最大的第一个数字就是result

代码

public int findBottomLeftValue(TreeNode root) {
        int[] result = helper(root, 0);
        return result[1];

    }
    public int[] helper(TreeNode root, int depth){
        if(root.left == null && root.right == null){
            //System.out.println(depth+1 + " "+ root.val);
            return new int[]{depth+1 , root.val};
        }
        int[] left = new int[]{-1, 0};
        int[] right = new int[]{-1, 0};

        if(root.left != null){
            left = helper(root.left, depth+1);
        }
        if(root.right != null){
            right = helper(root.right, depth+1);
        }

        if(left[0] >= right[0]){
            return left;
        }else{
            return right;
        }
    }

复杂度

时间：O(N) 空间：O(h) height

[RestlessBreeze]

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    queue<TreeNode*>q;
    int findBottomLeftValue(TreeNode* root) {
        TreeNode* ans;
        q.push(root);
        while(!q.empty())
        {
            ans = q.front();
            q.pop();
            if (ans->right) q.push(ans->right);
            if (ans->left) q.push(ans->left);
        }
        return ans->val;
    }
};

[huifeng248]

from collections import deque

# BFS, the leftmost value will appear first, and the level if greater than the max_level, leftmost value would be updated. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:

        max_level = float('-inf')
        left_most = root.val
        queue = deque([(root, 0)])

        while queue:
            current, level = queue.popleft()

            if level > max_level:
                max_level = level
                left_most = current.val

            if current.left:
                queue.append((current.left, level +1 ))
            if current.right:
                queue.append((current.right, level+1))

        return left_most

# time complexity: O(n), n is the number of nodes
# space complexity: O(n), n is the number of nodes

[joriscai]

思路

• 使用广度优先遍历
• 每次记录队列最左侧值，若当前层级都无子节点时，即为结果

  代码

  javascript

/*
 * @lc app=leetcode.cn id=513 lang=javascript
 *
 * [513] 找树左下角的值
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    if (!root) return null
    let res = root.val
    const queue = [root]
    while (queue.length) {
        res = queue[0].val
        let len = queue.length
        while (len) {
            const node = queue.shift()
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
            len--
        }
    }
    return res
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，访问一次节点即可

空间复杂度：O(n)，空间大小为节点最多那一层的节点数，最坏情况是，整个队列有n个节点

[X1AOX1A]

0513. 找树左下角的值

题目

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

思路：BFS

• BFS 遍历每一层，保留每一层最左侧的值
• tips: 通过每次对 queue 求 len，可以得到当前遍历层的节点个数

代码

from collections import deque
class Solution:
    def findBottomLeftValue(self, root):
        queue = deque()
        queue.append(root)
        while queue:
            length = len(queue)
            res = queue[0].val
            for _ in range(length):
                cur = queue.popleft()
                if cur.left:  queue.append(cur.left)
                if cur.right: queue.append(cur.right)
        return res

• 时间复杂度：O(n)，n 为节点个数
• 空间复杂度：O(n)，n 为节点个数，当二叉树为平衡二叉树时，最后一层将会有 2/n+1 个节点，此时空间复杂度为 O(n)

[harperz24]

• dfs

  class Solution:
  def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
      self.max_height = 0
      self.res = 0
      self.dfs(root, 1)
      return self.res
  
  def dfs(self, root, height):
      if not root:
          return
      height += 1
      if height > self.max_height:
          self.max_height = height
          self.res = root.val
  
      self.dfs(root.left, height)
      self.dfs(root.right, height)
  
  # dfs 
  # time: O(n)
  # space: O(h)

• bfs

  class Solution:
  def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
      queue = collections.deque()
      queue.append(root)
      left_bottom = 0
  
      while queue:
          size = len(queue)  
          # to save space, level lists are not needed
          for _ in range(size):
              node = queue.popleft()
  
              # append from right to left, so that the last node we traverse is the leftmost node
              if node.right:
                  queue.append(node.right)
              if node.left:
                  queue.append(node.left)
  
              # update left_bottom when iterating every level
              left_bottom = node.val
  
      return left_bottom
  
      # bfs, level order 
      # time: O(n)
      # space: O(n)

[JasonQiu]

• DFS

  class Solution:
  def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
      def dfs(root, depth):
          if not root:
              return
          cur_depth = depth + 1
          if cur_depth > self.max_depth:
              self.max_depth = cur_depth
              self.result = root.val
          dfs(root.left, cur_depth)
          dfs(root.right, cur_depth)
  
      self.max_depth = 0
      self.result = root.val
      dfs(root.left, 0)
      dfs(root.right, 0)
      return self.result

  Time: O(n) Space: O(h)

[Horace7]

function findBottomLeftValue(root) {
  let curLevel = [root];
  while (curLevel.length) {
    let nextLevel = [];
    for (let i = 0; i < curLevel.length; i++) {
      let node = curLevel[i];
      node.left && nextLevel.push(node.left);
      node.right && nextLevel.push(node.right);
    }
    if (!nextLevel.length) {
      return curLevel[0].val;
    }
    curLevel = nextLevel;
  }

  return curLevel[0].val;
}

[aswrise]

class Solution(object):
    def findBottomLeftValue(self, root):
        def recursion(nodes):
            if nodes == [] or nodes == [None]:
                return nodes
            else:
                next_level_nodes = []
                for node in nodes:
                    next_level_nodes.append(node.left) if node.left is not None else None
                    next_level_nodes.append(node.right) if node.right is not None else None

                if next_level_nodes == []:
                    return nodes[0].val
                else:
                    return recursion(next_level_nodes)

        return recursion([root])

[Bochengwan]

思路

层序遍历

代码

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int answer = root.val;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.offer(root);
        while(!nodeQueue.isEmpty()) {
            answer = nodeQueue.peek().val;
            int length = nodeQueue.size();
            for(int i = 0; i < length; i++) {
                TreeNode currNode = nodeQueue.poll();
                if(currNode.left != null) nodeQueue.offer(currNode.left);
                if(currNode.right != null) nodeQueue.offer(currNode.right);
            }
        }
        return answer;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为节点个数。
• 空间复杂度：O(N)

[lp1506947671]

思路

• 找到树的最后一行
• 找到那一行的第一个节点

代码

# DFS
class Solution1:

    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = collections.deque()
        queue.append(root)
        res = root.val
        while queue:
            length=len(queue)
            res = queue[0].val
            for _ in range(length):
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return res

# BFS
class Solution2:
    def __init__(self):
        self.res = 0
        self.max_deep = 0

    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:

        def dfs(root1: Optional[TreeNode], deep):
            if not root1:
                return
            if deep > self.max_deep:
                self.res = root1.val
                self.max_deep = deep

            dfs(root1.left, deep + 1)
            dfs(root1.right, deep + 1)

        self.res = root.val
        dfs(root, 0)
        return self.res

复杂度

时间复杂度:DFS:O(n) BFS:O(n)

空间复杂度:DFS:O(Q)Q为队列长度最坏为n BFS:O(Q)Q为树的高度

[ZhuMengCheng]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {

    let curHeight = 0;
    let curVal = 0;

    const dfs = (root, height) => {
        if (!root) {
            return;
        }
        height++;
        dfs(root.left, height);
        dfs(root.right, height);
        if (height > curHeight) {
            curHeight = height;
            curVal = root.val;
        }
    }

    dfs(root, 0);
    return curVal;

};

• 复杂度分析 时间复杂度：O(N) 空间复杂度：O(N)

[linlizzz]

思路

BFS，每一层从右往左遍历，更新值

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import collections
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        nodes = collections.deque()
        nodes.append(root)
        while nodes:
            node = nodes.popleft()
            val = node.val
            if node.right:
                nodes.append(node.right)
            if node.left:
                nodes.append(node.left)
        return val

复杂度分析

T(n) = O(n), n为树的结点数

S(n) = O(h), h为树的高度

[wangzh0114]

思路

• BFS DFS

  代码

  /*BFS*/
  class Solution1 {
  public:
  int findBottomLeftValue(TreeNode* root) {
      queue<TreeNode*> Q;
      TreeNode* ans = nullptr;
      Q.push(root);
      while(!Q.empty()){
          ans = Q.front();
          int size = Q.size();
          while(size--){
              TreeNode* curr = Q.front();
              Q.pop();
              if(curr->left) Q.push(curr->left);
              if(curr->right) Q.push(curr->right);
          }
      }
      return ans->val;
  }
  };

  /*DFS*/
  class Solution2 {
  public:
      int ret;
      int maxDepth = 0;
      void dfs(TreeNode* root, int depth){
          if(!root->left && !root->right){
              if(depth > maxDepth){
                  maxDepth = depth;
                  ret = root->val;
              }
              return;
          }
          else{
              if(root->left) dfs(root->left, depth + 1);
              if(root->right) dfs(root->right,depth + 1);
          }
      }
  
      int findBottomLeftValue(TreeNode* root) {
          dfs(root, 1);
          return ret;
      }
  };

  ---

  复杂度分析

• TC:O(N)，N为树的节点数
• SC:O(N)，BFS中N为队列Q的长度，DFS中N为树的高度

[texamc2]

func findBottomLeftValue(root TreeNode) (curVal int) { curHeight := 0 var dfs func(TreeNode, int) dfs = func(node *TreeNode, height int) { if node == nil { return } height++ dfs(node.Left, height) dfs(node.Right, height) if height > curHeight { curHeight = height curVal = node.Val } } dfs(root, 0) return }

[yingchehu]

思路

用 BFS，每一層都紀錄第一個節點的數字，走到最後一層就能得到答案

Code

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = collections.deque()
        q.append(root)
        ans = root.val
        while q:
            num = len(q)
            ans = q[0].val
            for _ in range(num):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

複雜度

Time: O(N) Space: O(Q) Q 為 queue 的大小

[kangliqi1]

class Solution { public int findBottomLeftValue(TreeNode root) { Queue queue = new LinkedList<>(); queue.offer(root); int val = root.val; while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node.right != null) { queue.offer(node.right); } if (node.left != null) { queue.offer(node.left); } val = node.val; } return val; } }

[Fuku-L]

思路

广度优先遍历，使用队列存储待遍历的节点，先存储根的右子树，再存左子树。保证最后遍历的节点为最底层 最左边 节点的值。

代码

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.offer(root);
        int res = -1;
        while(!bfs.isEmpty()){
            TreeNode cur = bfs.poll();
            res = cur.val;
            if(cur.right != null){
                bfs.offer(cur.right);
            }
            if(cur.left != null){
                bfs.offer(cur.left);
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为树的节点数。
• 空间复杂度：O(N)

[AstrKing]

思路

广度优先遍历，先加右，再加左，保证最后遍历的节点为最底层最左边节点的值。

代码

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.offer(root);
        int res = -1;
        while(!bfs.isEmpty()){
            TreeNode cur = bfs.poll();
            res = cur.val;
            if(cur.right != null){
                bfs.offer(cur.right);
            }
            if(cur.left != null){
                bfs.offer(cur.left);
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n) 空间复杂度：O(n)

[kofzhang]

思路

深度优先搜索

复杂度

时间复杂度：O(n) 空间复杂度：O(h)

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        def findBottom(node,curdep):            
            c = curdep+1,node.val
            l = findBottom(node.left,c[0]) if node.left else (-1,-1)
            r = findBottom(node.right,c[0]) if node.right else (-1,-1)
            return max([c,l,r],key=lambda x:x[0])

        return findBottom(root,0)[1]

[liuajingliu]

解题思路

BFS

代码实现

javaScript

/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function(root) {
if(!root) return null;
const queue = [root]
let mostLeft = null;
while(queue.length > 0){
let curLevelSize = queue.length
mostLeft = queue[0]
for(let i = 0; i < curLevelSize; i++){
const curNode = queue.shift();
curNode.left && queue.push(curNode.left)
curNode.right&& queue.push(curNode.right)
}
}
return mostLeft.val
};

复杂度分析

• 时间复杂度 $O(N)$ N为二叉树的节点
• 空间复杂度 $O(N)$ N为二叉树的节点

[Leonalhq]

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        # BFS, find by level
        queue = collections.deque()
        queue.append(root)
        top = None
        while queue:
            length = len(queue)
            top = queue[-1]
            for _ in range(length):
                head = queue.popleft()
                if head.right:
                    queue.append(head.right)
                if head.left:
                    queue.append(head.left)

        return top.val

[JadeLiu13]

class Solution: def findBottomLeftValue(self, root: TreeNode) -> int: max_depth = -float("INF") leftmost_val = 0

    def __traverse(root, cur_depth): 
        nonlocal max_depth, leftmost_val
        if not root.left and not root.right: 
            if cur_depth > max_depth: 
                max_depth = cur_depth
                leftmost_val = root.val  
        if root.left: 
            cur_depth += 1
            __traverse(root.left, cur_depth)
            cur_depth -= 1
        if root.right: 
            cur_depth += 1
            __traverse(root.right, cur_depth)
            cur_depth -= 1

    __traverse(root, 0)
    return leftmost_val

[zhangjiahuan17]

class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: curlevel = collections.deque() curlevel.append(root) while curlevel: length = len(curlevel) res = curlevel[0].val for _ in range(length): cur = curlevel.popleft() if cur.left: curlevel.append(cur.left) if cur.right: curlevel.append(cur.right) return res

[CruiseYuGH]

关键点

代码

• 语言支持：Python3

Python3 Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        # dfs
        curVal = curHeight = 0
        def dfs(node,deep_num):
            if node is None :
                return 
            dfs(node.left,deep_num+1)
            dfs(node.right,deep_num+1)
            nonlocal curVal, curHeight
            if  deep_num+1>curHeight:
                curVal = node.val
                curHeight = deep_num+1
        dfs(root,0)
        return curVal

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$