【Day 16 】2022-04-16 - 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
 

[maggiexie00]

思路

bfs，唯一特殊一些的地方在于，入队顺序是先右孩子再左孩子。

代码

    def findBottomLeftValue(self, root):

        queue=deque()
        queue.append(root)
        n=len(queue)

        while queue:
            for _ in range(n):
                node=queue.popleft()
                tmp=node.val

                if node.right:
                    queue.append(node.right)
                if node.left:
                    queue.append(node.left)

    return tmp

复杂度

时间o(n) 空间 o(n)

[rzhao010]

Code

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

[xil324]

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = 0; 
        queue = collections.deque(); 
        queue.append(root); 
        while queue:
            res = queue[0].val; 
            for _ in range(len(queue)):
                curr = queue.popleft(); 
                if curr.left:
                    queue.append(curr.left); 
                if curr.right:
                    queue.append(curr.right); 
        return res; 

时间复杂度： O(N)

空间复杂度： O(N); worst case

[Yongxi-Zhou]

思路

BFS，然后返回最左边 bottom 的节点

代码

    # 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:
            q = deque()
            q.append(root)
            res = []
            while q:
                size = len(q)
                temp = []
                for i in range(size):
                    cur = q.popleft()
                    temp.append(cur.val)
                    if cur.left:
                        q.append(cur.left)
                    if cur.right:
                        q.append(cur.right)
                res.append(temp[:])
            return res[-1][0]

复杂度

time O(N) space O(1)

[zqwwei]

Code

    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        maxDepth = 0
        val = None
        def findBLV(root, depth):
            nonlocal maxDepth, val
            if not root: return
            if root and maxDepth < depth:
                val = root.val
                maxDepth = depth

            depth += 1
            findBLV(root.left, depth)
            findBLV(root.right, depth)

        findBLV(root, 1)
        return val

Complexity

O(n)
O(log n)

[ZacheryCao]

Idea

BFS

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:
        stack = collections.deque()
        stack.append(root)
        ans = root.val
        while stack:
            l = len(stack)
            ans = stack[0].val
            for _ in range(l):
                cur = stack.popleft()
                if cur.left:
                    stack.append(cur.left)
                if cur.right:
                    stack.append(cur.right)
        return ans

Complexity:

Time: O(N) Space: O(H). H the widest layer

[james20141606]

Day 16: 513. Find Bottom Left Tree Value (binary tree, BFS, DFS)

• Problem Link

  • 513. Find Bottom Left Tree Value

• Ideas

  • There are two solutions, DFS and BFS
  • DFS: it is natural to use DFS to traverse from root to each leaf and locate the first node which is at the deepest layer. We could define a DFS function inside the findBottomLeftValue function. Note that we need both current position and current layer depth to be passed to the DFS function. The tricky part is we should maintain two global values to record the leftmost node and the deepest layer, outside the DFS but in __init__, so DFS doesn't need to return value. We could have recursion which requires root's both `left and right node. We won't update the two global values only if the new layer's depth is deeper than the global value! Complexity: Time: O(# nodes); Space: O(depth of the tree), (worst case is # nodes which degenerate to a linked list)
  • BFS: use BFS template, we could have deque to record the current leftmost node. The while loop iterate through each layer. the for loop go over each node in one layer. we pop each node in the layer and append child nodes in the next layer for the next loop in while. Then the res is the bottom left value. Time: O(# nodes); Space: O(q), (q is length of deque, the worst case is # nodes/2 if the BST is full, the deepest layer will have $\frac{n}{2}$ nodes)

• Complexity: (DFS)

  • Time: O(# nodes)
  • Space: O(depth of the tree)

• Code

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

#BFS
import collections
class Solution(object):
    def findBottomLeftValue(self, root):
        queue = collections.deque()
        queue.append(root)
        while queue:
            length = len(queue)
            #print ('length',length)
            #print ('current value in deque',[i.val for i in queue])
            res = queue[0].val
            for _ in range(length):
                cur = queue.popleft()
                #print (cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            #print ('current value in deque after append',[i.val for i in queue])
        return res

• other resources:

[MoonLee001]

思路

dfs求二叉树最大深度，根据深度值判断更新最左侧值

代码

var findBottomLeftValue = function(root) {
    let res;
    let maxDepth = -1;
    const dfs = (root, depth) => {
        if (root == null) {
            return;
        }
        if (depth > maxDepth) {
            res = root.val;
            maxDepth = depth;
        }

        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);

    }
    dfs(root, 0);
    return res;
}

复杂度分析

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

[wwang4768]

Idea
Depth-firs search general strategy + recursion

Code

int highest=0,res;
void calc(TreeNode* root,int level){
    if(!root)
        return;
    if(highest<level){     //store first value of each level
       res=root->val;
        highest=level;    //update level
    }
    calc(root->left,level+1);    //recursive call for next level
    calc(root->right,level+1);  
}
int findBottomLeftValue(TreeNode* root) {
    calc(root,1);
    return res;
}

Complexity
O(n)
O(n)

[FutureFields]

Idea: DFS

class Solution { public: TreeNode targetNode; int maxHeight = 0; void dfs( TreeNode node, int curHeight){ if( !node->left && !node->right ){ if( curHeight > maxHeight) { targetNode = node; maxHeight = curHeight; } return; } if( node->left ) dfs( node->left, curHeight+1 ); if( node->right ) dfs( node->right, curHeight+1 ); } int findBottomLeftValue(TreeNode* root) { dfs( root, 1 ); return targetNode->val; } };

Space: O(n), Time:O(n)

[houmk1212]

思路

层次遍历，从右向左输出即可，最后一个元素就是待求节点。

代码

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null)
            return -1;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        int res = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }
            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            res = tmp.val;
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(N) N是树的节点个数
• 空间复杂度： O(N)

[C2tr]

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = [root]
        ans = root.val
        while queue:
            ans = queue[0].val
            n = len(queue)
            for i in range(n):
                node = queue[0]
                del queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

参考来自:hhh-v0大佬

[kite-fly6618]

思路：

DFS

代码：

var findBottomLeftValue = function(root) {
    let maxdepth = 1
    let leftValue = root.val
    let dfs = function(root,depth) {
        if(depth>maxdepth&&!root.left&&!root.right) {
            leftValue = root.val
            maxdepth = depth
        }
        root.left&&dfs(root.left,depth+1)
        root.right&&dfs(root.right,depth+1)
    }
    dfs(root,1)
    return leftValue
}

复杂度：

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

[currybeefer]

思路：层序遍历就好啦，用一个数组保存最后一组的row的信息，然后返回数组的第一个元素 代码：

int findBottomLeftValue(TreeNode* root) 
    {
        if(root==nullptr) return 0;

        vector<int> ans;
        queue<TreeNode*> qe;
        qe.push(root);

        while(!qe.empty())
        {
            vector<int> row;
            int count=qe.size();
            while(count!=0)
            {
                TreeNode* a=qe.front();
                qe.pop();

                row.push_back(a->val);

                if(a->left!=nullptr)
                    qe.push(a->left);

                if(a->right!=nullptr)
                    qe.push(a->right);

                count--;
            }
            ans=row;
        }
        return ans[0];
}

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

[hyh331]

Day16 思路

思路：dfs+递归

1. 确定递归函数的参数和返回值，参数为根节点和此时的深度。返回值为空。
2. 确定终止条件，当遍历到是空节点，直接返回。
3. 利用前序遍历。判断当前深度 curDepth 是否为大于最大深度 maxDepth ，若大于，则将当前的节点值赋给 left ，同时更新最大深度的值。这种做法可以保证，当遇到当前深度大于最大深度时，赋值给 left 的值一定是这一层最左边的节点值，因为后面的都是同一层，不满足大于条件。若是判断大于等于，则 left 将被赋为这一层的最右节点的值。

   class Solution {
   public:
   int left=0;
   int maxDepth=0;
   void dfs(TreeNode* root,int curDepth){
       if(root==NULL)  return;
       if(curDepth>maxDepth){
           left=root->val;
       }else{
           left=left;
       }
       maxDepth = max(curDepth, maxDepth); 
       dfs(root->left, curDepth + 1);
       dfs(root->right, curDepth + 1);
   }
   int findBottomLeftValue(TreeNode* root) {
       dfs(root,1);
       return left;
   }
   };

   复杂度分析

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

[Magua-hub]

class Solution {
public:
    int maxLevel = 0, res = 0;
    int findBottomLeftValue(TreeNode* root) {
        return dfs(root, 1);
    }

    int dfs(TreeNode* root, int u) {
        if(!root) return root->val;
        if(u > maxLevel) {
            res = root->val;
            maxLevel = u;
        }
        if(root->left) dfs(root->left, u + 1);
        if(root->right) dfs(root->right, u + 1);
        return res;
    }
};

[PFyyh]

题目地址(513. 找树左下角的值)

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

题目描述

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

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

 

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

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

 

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1 

前置知识

• 二叉树的广度遍历

公司

• 暂无

思路

关键点

• 背广度遍历模板，定义一个List，存储没有遍历的节点。获取每层的节点数，将值存入List（改下模板，从右到左遍历，就不用存）。最后一个list的第一个元素就是最深层的最左元素。

代码

• 语言支持：Java

Java Code:

/**
 * 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) {
    //如果没值，直接返回
       if (root==null){
           return 0;
       }
       //创建List,存储每层节点元素
        List<List<Integer>> values = new LinkedList<>();
       //创建List，存储待遍历节点
        LinkedList<TreeNode> needShowList = new LinkedList<>();
       //第一次把根节点加入其中
        needShowList.add(root);
        //遍历知道List没有值为止
        while (needShowList.size()>0){
            //获取当前层，节点个数
            int size = needShowList.size();
            //获取当前层第一个元素
            //创建当前层List
            LinkedList<Integer> list = new LinkedList<>();
            //遍历当前节点
            for (int i = 0; i < size; i++) {
                TreeNode index = needShowList.pollFirst();
                list.add(index.val);
                if (index.left!=null){
                    needShowList.add(index.left);
                }
                if (index.right!=null){
                    needShowList.add(index.right);
                }
            }
            values.add(list);
        }
        return values.get(values.size()-1).get(0);
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(N)$，N是节点数目
• 空间复杂度：$O(Q)$，最多能存满二叉树,Q是队列长度

[KelvinG-LGTM]

思路

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
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root: 
            return -1 
        queue = deque()
        queue.append(root)
        res = None
        while queue: 
            q_len = len(queue)
            res = queue[0].val
            for _ in range(q_len): 
                cur = queue.popleft()
                if cur.left: 
                    queue.append(cur.left)
                if cur.right: 
                    queue.append(cur.right)

        return res

复杂度分析

时间复杂度

O(N)

空间复杂度

O(N) 高度 = logN. 第N层有 2 ^ (logN) = N

[caterpillar-0]

思路

深度优先搜索，DFS，利用全局变量，以及dfs递归传递当前深度，时间复杂度o(n),空间复杂度o(n)

代码

class Solution {
public:
    int left=0,maxdepth=0;
    //递归函数，结束条件
    void dfs(TreeNode* root,int dpth){
        if(root==nullptr){
            return;
        }
        if(dpth>maxdepth){
            left=root->val;
            maxdepth++;
        }
        dfs(root->left,dpth+1);
        dfs(root->right,dpth+1);
    }
    int findBottomLeftValue(TreeNode* root) {
        dfs(root,1);
        return left;
    }
};

复杂度分析

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

  思路

  广度优先搜索，BFS，每次只记录每一层的头结点，处理一层

  代码

  class Solution {
  public:
  //广度优先搜索，队列
  int findBottomLeftValue(TreeNode* root) {
      queue<TreeNode*> Q;
      int left;
      if(root==nullptr){
          return 0;
      }
      Q.push(root);
      while(!Q.empty()){
          int size=Q.size();
          left=Q.front()->val;//只保留每一层节点的头结点
          while(size--){//每次处理一层节点
              TreeNode* tmp=Q.front();
              Q.pop();
              if(tmp->left!=nullptr){
                  Q.push(tmp->left);
              }
              if(tmp->right!=nullptr){
                  Q.push(tmp->right);
              }
          } 
      }
      return left;
  }
  };

  复杂度分析

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

[xixiao51]

Idea

DFS(preorder) / BFS(from right to left)

Code

DFS

class Solution {
    int bottom = 0;
    int val;

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

    private void dfs(TreeNode root, int level) {
            if(root != null) {
                if(root.left == null && root.right == null) {
                    if(level > bottom) {
                        val = root.val;
                        bottom = level;
                    }
                }
                dfs(root.left, level + 1);
                dfs(root.right, level + 1);
            }
        }
}

BFS

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

Complexity

DFS:

• Time：O(N)
• Space：O(height)

BFS

• Time：O(N)
• Space：O(N)

[forestie9]

Ideas

Tree level traversal and return last level right item

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        res = []
        def dfs(root, level):
            if not root: return
            if level >= len(res):
                res.append([])
            res[level].append(root.val)
            dfs(root.left, level + 1)
            dfs(root.right, level + 1)

        dfs(root, 0)    
        return res[-1][0]

complexity

O(n) time and space

[Jessie725]

Idea

BFS: record the left most node value before we expend each level i.e. peek element of queue

Code

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            return -1;
        }

        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int left = 0;
        while(!q.isEmpty()) {
            int levelSize = q.size();
            left = q.peek().val;
            for(int i = 0; i < levelSize; i++) {
                TreeNode curr = q.poll();
                if (curr.left != null) {
                    q.offer(curr.left);
                }
                if (curr.right != null) {
                    q.offer(curr.right);
                }
            }
        }
        return left;
    }
}

Complexity

Time: O(n) reach to every node of the tree Space: O(q) largest size of queue

[Venchyluo]

BFS level traversal. 保留每一层第一个node.val 就是最左边的leaf.val

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

        queue = collections.deque([root])
        res = root.val
        while queue:
            res = queue[0].val
            for _ in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return res

time complexity: O(N)
space complexity: O(width)

DFS stack 做法， 缺点就是保存了所有node.val。 蹲一个明天的官方答案

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
       # stack
        stack = []
        depth = -1
        res = []

        while root or stack:
            if root:
                depth += 1
                stack.append([root,depth])
                if len(res) == depth:
                    res.append([])
                res[depth].append(root.val)
                root = root.left
            else:
                root, depth = stack.pop()
                root = root.right

        return res[-1][0]

time complexity: O(N)
space complexity: O(N)

[shawnhu23]

Idea

BFS and record the left most value on each level

Code

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int left = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                if (i == 0) {
                    left = cur.val;
                }
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
        }
        return left;
    }
}

Complexity

time: O(n) space: O(n)

[CarrieyqZhang]

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

    public void dfs(TreeNode root, int curDepth)
    {
        if(root == null)
            return;
        left = curDepth > maxDepth ? root.val : left;
        maxDepth = Math.max(curDepth, maxDepth); 
        dfs(root.left, curDepth + 1);
        dfs(root.right, curDepth + 1);
    }

time/space complexity: O(n)

[nancychien]

ideas: DFS

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        level, leftmost = [root], root.val
        while level:
            leftmost = level[0].val
            level = [c for n in level for c in [n.left, n.right] if c]
        return leftmost

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

[zzz607]

思路

前序遍历，每找到一个叶子，判断是否大于之前找到的叶子节点的深度。 若是大于的话，则替换为当前的叶子节点的深度和值，遍历完所有叶子 节点即得到最左值

代码

func findBottomLeftValue(root *TreeNode) int {
    var height, value int

    var search func(*TreeNode, int)
    search = func(node *TreeNode, hh int) {
        hh++
        if node.Left == nil && node.Right == nil {
            if hh > height {
                height = hh
                value = node.Val
            }
            return
        }

        if node.Left != nil { search(node.Left, hh) }
        if node.Right != nil { search(node.Right, hh) }
    }

    search(root, 0)
    return value
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)，栈除外

[carterrr]

/**

• 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) { int[] res = new int[]{-1, 0}; dfs(root, res, 0); return res[1]; }

  // 二元组 level val public void dfs(TreeNode node, int[] bottomLeft, int h) { // h 水平坐标 if(h > bottomLeft[0]){ bottomLeft[0] = h; bottomLeft[1] = node.val; } if(node.left != null) dfs(node.left, bottomLeft, h + 1); if(node.right != null) dfs(node.right, bottomLeft, h + 1); } }

[sallyrubyjade]

思路

BFS，每一层取queue中第一个元素的值，遍历完，更新为最后一层第一个元素的值。

代码

/**
 * 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 queue = [root];

    let left;
    while (queue.length) {
        let curNum = queue.length;

        left = queue[0].val;
        while (curNum--) {
            let node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return left;
};

复杂度分析

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

[Ellie-Wu05]

思路：双向队列

从右往左bfs遍历，不断leftpop 最后剩下的是答案

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return None
        queue = collections.deque([root])
        ans = None

        while queue:
            size = len(queue)
            for _ in range(size):
                ans = node = queue.popleft()
                if node.right:
                    queue.append(node.right)
                if node.left:
                    queue.append(node.left)
        return ans.val

复杂度分析

时间 On？ 空间 Oh? 不确定。。。

[wenliangchen]

思路

队列BFS

代码

public int findBottomLeftValue(TreeNode root) {

    int ans = 0;

    Queue<TreeNode> q = new LinkedList();
    q.add(root);
    while(!q.isEmpty()){
        int count = q.size();
        for(int i = 0; i<count; i++){
            TreeNode curr = q.poll();
            if(i==0)
                ans = curr.val;
            if(curr.left!=null)
                q.add(curr.left);
            if(curr.right!=null)
                q.add(curr.right);
        }
    }
    return ans;
}

复杂度

O(N)

[liuguang520-lab]

思路

使用bfs，对每一层进行一次循环，并且输出循环开始的数据就是每一层最左边的位置。

code

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int left;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0; i<size; i++)//每一层的进行循环
            {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left != nullptr)
                {
                    q.push(cur->left);
                }
                if(cur->right != nullptr)
                {
                    q.push(cur->right);
                }
                if(i == 0)//最左边的值
                {
                    left = cur->val;
                }
            }
        }
        return left;
    }
};

复杂度分析

• 时间复杂度 O(N), 每一个节点都会遍历
• 空间复杂度O(N), 保存每一层的数量

[ShawYuan97]

代码

• 语言支持：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:
        """
        给定一个二叉树的根节点root，找出该二叉树最底层最左边节点的值
        """
        """
        采用层次遍历，然后选择最后一层的最左边的一个
        """
        if not root:
            return 
        q = deque()
        q.append((root,0))
        max_level = 0
        value = root.val
        while q:
            node,level = q.popleft()
            if not node.left and not node.right:
                if max_level < level:
                    max_level = level
                    value = node.val
            if node.left:
                q.append((node.left,level+1))
            if node.right:
                q.append((node.right,level+1))
        return value

复杂度分析

令 n 为数组长度。

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

[ha0cheng]

思路：找到最后一层中最左边的节点，DFS递归或者层次遍历。

1. 递归 写一个函数，找到以这个节点为根节点的最后一层最左边的节点的值，同时返回深度。则递归过程为： 返回左子树的最左节点和右子树的最左节点中深度最深的那个，如果同样深则返回左子树的最左节点。

时间复杂度: O(N), 需要遍历一遍所有节点 空间复杂度: O(depth)，是递归所占用的空间，为树的深度

2.层次遍历 逐层的遍历一棵树，从左到右访问，访问完一个节点将他的左右子节点加入到队列中，进行下次遍历，每一层最左的节点即是刚开始遍历这一层时的最左边节点。

时间度复杂度：O(N), 需要遍历一遍所有节点 空间复杂度: O(Q)，是队列最多需要保存的一层的节点个数，满二叉树下与N同阶

递归代码如下：

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        def DFS_findvalue(root,cur_depth):
            if not root.left and not root.right:
                return root.val, cur_depth

            left_depth = cur_depth
            right_depth = cur_depth

            if root.left:
                left_val, left_depth = DFS_findvalue(root.left, cur_depth+1)
            if root.right:
                right_val, right_depth  = DFS_findvalue(root.right, cur_depth+1)
            if left_depth >= right_depth:
                return left_val, left_depth
            else:
                return right_val, right_depth

        val, depth = DFS_findvalue(root,0)
        return val

层次遍历代码如下：

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

        return res

[YuyingLiu2021]

#BFS遍
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        #时间复杂度: O(N)
        #空间复杂度: O(N)
        queue = [root]
        res = root.val

        while queue:
            res = queue[0].val
            n =len(queue)
            for i in range(n):
                node = queue[0]
                del queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

#优化一下
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = [root]
        while queue:
            node = queue.pop(0) 
            if node.right:#先右后左
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val

[miss1]

思路

BFS, 层序遍历，用一个队列记录每一层的所有节点，队列的第一个数据就是该层最左边的节点

代码

var findBottomLeftValue = function(root) {
  let currentLevel = [root];
  let res = root.val;
  while(currentLevel.length > 0) {
    let nextLevel = [];
    for (let i = 0; i < currentLevel.length; i++) {
      if (currentLevel[i].left) nextLevel.push(currentLevel[i].left);
      if (currentLevel[i].right) nextLevel.push(currentLevel[i].right);
    }
    if (nextLevel.length > 0) res = nextLevel[0].val;
    currentLevel = nextLevel;
  }
  return res;
};

复杂度分析

• time: O(n)
• space: O(q), q为队列长度

[KWDFW]

Day16

513、找树左下角的值

javascript #树

思路

1、采用树的层序遍历，遍历结束后，取最后一行的左节点返回

2、把每一层存在一个数组里

3、每次循环都通过遍历上一层的数组，把下一层再存入数组

4、当数组中存的都是空节点时，循环结束

代码

var findBottomLeftValue = function(root) {
    let curLevel=[]//存储树的上一层的数组
    curLevel.push(root)
    let res=root.val//最后的结果
    while(curLevel.length){//当数组中存放的都是空节点时，树的层序遍历结束
        let nextLevel=[]//存储树的下一层的数组
        for(let i=0;i<curLevel.length;i++){//遍历上一层，把下一层放进去
            if(curLevel[i].left) nextLevel.push(curLevel[i].left) 
            if(curLevel[i].right) nextLevel.push(curLevel[i].right) 
        }
        res=curLevel[0].val//取当前遍历层的左下节点的值
        curLevel=nextLevel//遍历结束后，换到下一层
    }
    return res
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[BiN214]

思路

层次遍历

代码

 Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int last = 0;
            for(int i = 0; i < size; i++){
                TreeNode p = queue.poll();
                if(p.right != null) queue.offer(p.right);
                if(p.left != null) queue.offer(p.left);
                last = p.val;
            }
            if(queue.isEmpty()) return last;
        }
        return root.val;

[Zhen-Guan]

# 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 __init__(self):
        self.depth = 0
        self.res = 0
        self.max_depth = 0
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        # solution 1
        # queue = collections.deque()
        # queue.append(root)
        # res_l = []
        # while queue:
        #     n = len(queue)
        #     level = []
        #     for i in range(n):
        #         cur = queue.popleft()
        #         level.append(cur)
        #         if cur.left:
        #             queue.append(cur.left)
        #         if cur.right:
        #             queue.append(cur.right)
        #     res_l.append(level)
        # return res_l[-1][0].val

        # solution 2
        self.traverse(root)
        return self.res.val

    def traverse(self, root):
        if root == None:
            return
        self.depth += 1
        if self.depth > self.max_depth:
            self.max_depth = self.depth
            self.res = root
        self.traverse(root.left)
        self.traverse(root.right)
        self.depth -= 1

[freedom0123]

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> list = new LinkedList<>();
        if(root == null) return -1;
        list.add(root);
        int res = root.val;
        int floor = 1;
        while(!list.isEmpty()) {
            for(int i = 0;i < floor; i++) {
                 TreeNode node = list.getFirst();
                 list.removeFirst();
                 if(i == 0) res = node.val;
                 if(node.left != null) list.add(node.left);
                 if(node.right != null) list.add(node.right);
            }
            floor = list.size();
        }
        return res;
    }
}

[physicshi]

思路

bfs

代码

var findBottomLeftValue = function (root) {
  if (!root) return null;
  const queue = [root];
  let Left;
  while (queue.length) {
    let curLevel = queue.length;
    Left = queue[0];
    for (let i = 0; i < curLevel; i++) {
      let curNode = queue.shift();

      curNode.left && queue.push(curNode.left);
      curNode.right && queue.push(curNode.right);
    }
  }
  return Left.val;
};

复杂度

• 时间复杂度：O(n)，节点个数，对每个节点访问一次
• 空间复杂度：O(max_size)，层最大宽度

[freedom0123]

原题链接

思路

• BFS
• 队列中只会保存一层的节点，每次会将上一层的点全部出队，并将这一层的点全部入队，这样队头元素就是每一层最左边的点。
• 时间复杂度：O(n)

  代码

  class Solution {
  public int findBottomLeftValue(TreeNode root) {
      LinkedList<TreeNode> list = new LinkedList<>();
      if(root == null) return -1;
      list.add(root);
      int res = root.val;
      int floor = 1;
      while(!list.isEmpty()) {
          for(int i = 0;i < floor; i++) {
               TreeNode node = list.getFirst();
               list.removeFirst();
               if(i == 0) res = node.val;
               if(node.left != null) list.add(node.left);
               if(node.right != null) list.add(node.right);
          }
          floor = list.size();
      }
      return res;
  }
  }

[dzwhh]

【Day 16】513.Find Bottom Left Tree Value「找树左下角的值」

• 题目地址: https://leetcode-cn.com/problems/find-bottom-left-tree-value/

题目描述

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

示例 1

输入: root = [2,1,3] 输出: 1

示例 2

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

前置知识

• 树
• DFS

思路

通过DFS递归找出深度最深的左叶子节点的值

代码

• js 版本

const 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 === null)
    return null;

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

复杂度分析

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

[maybetoffee]

class Solution {
    //level traversal, when we reach the maxDepth, the first one is target
    int currDepth = 0;
    int maxDepth = 0;
    TreeNode leftMost = null;
    public int findBottomLeftValue(TreeNode root) {
        traverse(root);
        return leftMost.val;
    }

    void traverse(TreeNode root){
        if(root == null) return;

        currDepth++;
        if(currDepth > maxDepth){
            maxDepth = currDepth;
            leftMost = root;
        }
        traverse(root.left);
        traverse(root.right);
        currDepth--;
    }
}

[EggEggLiu]

思路

dfs找深度最大的节点值记录

代码

var findBottomLeftValue = function(root) {
    let res;
    let deepest = 0;
    function dfs(node, depth) {
        if (!node) {
            return;
        }
        if (depth > deepest) {
            res = node.val;
            deepest = depth;
        }
        dfs(node.left, depth + 1);        
        dfs(node.right, depth + 1);
    }
    dfs(root, 1);
    return res;
};

[oneline-wsq]

思路

广度优先搜索

代码

# 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:
        """广度优先"""
        queue=[root]
        ans=root.val
        while queue:
            ans=queue[0].val
            n=len(queue)
            for i in range(n):
                node=queue[0]
                del queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

复杂度分析

时间复杂度：O(N）

空间复杂度：O(Q)

[linjunhe]

思路

• 设置最大深度maxDepth为-1，left值为0；
• 当当前深度depth大于maxDepth时，更新maxDepth和left值；
• 往左右递归时深度+1

Code

class Solution:

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

        def dfs(root, depth):
            if not root: return
            if depth > maxDepth_left[0]:
                maxDepth_left[0] = depth
                maxDepth_left[1] = root.val
            dfs(root.left, depth+1)
            dfs(root.right, depth+1)

        maxDepth_left = [-1, 0]
        dfs(root, depth=0)
        return maxDepth_left[1]

复杂度分析

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

[xingchen77]

思路

层次遍历

代码

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

复杂度

空间 O(n) \ 时间 O(n)

[zhishinaigai]

思路

dfs

代码

class Solution {
public:
    int left,maxd=-1;
    int findBottomLeftValue(TreeNode* root) {
        dfs(root,0);
        return left;
    }
    void dfs(TreeNode *root,int dep){
        if(!root) return;
        if(dep>maxd){
            left=root->val;
            ++maxd;
        }
        dfs(root->left,dep+1);
        dfs(root->right,dep+1);
    }

};

[LQyt2012]

思路

层序遍历，每一层第一次出队的节点就是二叉树最左边的节点。

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = collections.deque([root])
        left_num = root.val
        while queue:
            n = len(queue)
            for i in range(n):
                if i == 0:
                    node = queue.popleft()
                    left_num = node.val
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    node = queue.popleft()
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
        return left_num

func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    leftNum := root.Val
    for len(queue) != 0 {
        n := len(queue)
        for i:=0;i<n;i++ {
            if i == 0{
                node := queue[0]
                queue = queue[1:]
                leftNum = node.Val
                if node.Left != nil {
                    queue = append(queue, node.Left)
                }
                if node.Right != nil {
                    queue = append(queue, node.Right)
                }
            } else {
                node := queue[0]
                queue = queue[1:]
                if node.Left != nil {
                    queue = append(queue, node.Left)
                }
                if node.Right != nil {
                    queue = append(queue, node.Right)
                }
            }
        }
    }
    return leftNum
}

复杂度分析

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