【Day 16 】2023-06-25 - 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
 

[bi9potato]

Approach

DFS, inorder traversal.

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 {

    int maxDepth = 0;
    int currDepth = 0;

    int res;

    public int findBottomLeftValue(TreeNode root) {

        dfs(root);

        return res;

    }

    private void dfs(TreeNode root) {

        if (root== null) return;

        currDepth++;

        dfs(root.left);
        if (root.left == null && root.right == null) {
            if (currDepth > maxDepth) {
                maxDepth = currDepth;
                res = root.val;
            }

        }

        dfs(root.right);

        currDepth--;

    }

}

Complexity Analysis

• Time $\mathcal{O}(N)$
• Space $\mathcal{O}(N)$

[SoSo1105]

思路

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

代码

# 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 = collections.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)
• 空间复杂度：O(N)

[Beanza]

思路

二叉树先序遍历 用数组存储所有二叉树路径的字符串，最后转换为整数后求和

代码

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 sumNumbers(self, root: Optional[TreeNode]) -> int: """ :type root: TreeNode :rtype: int """ path = '' result = []

    self.helper(root, path, result)

    return sum([int(path) for path in result])

def helper(self, root, path, result):
    if not root:
        return 

    path += str(root.val)

    if not root.left and not root.right:
        result.append(path)

    self.helper(root.left, path, result)
    self.helper(root.right, path, result)

复杂度分析

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

[freesan44]

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func findBottomLeftValue(_ root: TreeNode?) -> Int {
        var queue = [TreeNode?]()
        queue.append(root)
        var res = 0
        while !queue.isEmpty {
            let length = queue.count
            res = queue[0]?.val ?? 0
            for _ in 0..<length {
                let cur = queue.removeFirst()
                if let left = cur?.left {
                    queue.append(left)
                }
                if let right = cur?.right {
                    queue.append(right)
                }
            }
        }
        return res
    }
}

[zhaoygcq]

思路

• 使用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) {
    let res = [];
    if(!root) return root;
    const queue = [root];
    while(queue.length) {
        let len = queue.length;
        let temp = [];
        while(len--) {
            const top = queue.shift();
            temp.push(top.val);
            if(top.left) {
                queue.push(top.left);
            }
            if(top.right) {
                queue.push(top.right);
            }
        }
        res.push(temp);
    }
    return res.pop().shift()
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[mo660]

思路

使用dfs遍历树，记录深度，如果当前深度大于最大深度，就舍弃之前的深度

代码

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:
    int res;
    int maxHeight;
    void dfs(TreeNode* root, int height)
    {
        if (nullptr == root)
            return;
        height++;
        dfs(root->left, height);
        dfs(root->right, height);
        if (height > maxHeight)
        {
            res = root->val;
            maxHeight = height;
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        res = root->val;
        dfs(root, 0);
        return res;
    }
};

[Diana21170648]

思路

bfs找最后一层第一个元素，一共queue dfs找最深层最后一个元素

代码

import collections
class Solution(object):
    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):#处理当前层的所有节点
                cur=queue.popleft()#如果本层不为空，则队列第一个值弹出，为本层腾地方
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return res

复杂度分析

• 时间复杂度：O(N)，其中 N 为节点数。
• 空间复杂度：O(q)，q为队列的长度，最坏情况下为完全二叉树，此时，q=n

[Alexno1no2]

# #广度优先搜索, 分层搜索，每层记录最左边的结点，最深一层记录的即所求结点
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         queue, ans = deque([root]), None
#         while queue:
#             ans = 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 ans

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

[snmyj]

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
            queue<TreeNode*> que;
            que.push(root);
            int obj;
            while(!que.empty()){
                int lenth=que.size();
                int s=lenth;

                while(lenth!=0){

                    TreeNode *curnode=que.front();
                    if(lenth==s)  obj=que.front()->val;
                    que.pop();
                    if(curnode->left)que.push(curnode->left);
                    if(curnode->right)que.push(curnode->right);
                    lenth--;

                }

            }

        return obj;
    }
};

O(n),n为树节点个数。

[jennyjgao]

public class MedianFindBottomLeftValue513 {
    //最深且最左的value==> BFS后最后一层的第一个值 => Queue
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if (root.right != null) queue.offer(root.right);
            if (root.left != null) queue.offer(root.left);
        }
        return root.val;
    }

}

[chang-you]

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)
        return node.val

[Master-guang]

// 层序遍历：
var findBottomLeftValue = function(root) {
    //考虑层序遍历 记录最后一行的第一个节点
    let queue = [];
    if(root === null){
        return null;
    }
    queue.push(root);
    let resNode;
    while(queue.length){
        let length =  queue.length;
        for(let i = 0; i < length; i++){
            let node = queue.shift();
            if(i === 0){
                resNode = node.val;
            }
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return resNode;
};

[joemonkeylee]

function findBottomLeftValue(root: TreeNode | null): number {
    let curVal: number;
    const dfs = (root, height) => {
        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;
};

[GuitarYs]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findBottomLeftValue(root):
    queue = [root]
    leftmost = root.val

    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.pop(0)
            if i == 0:
                leftmost = node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return leftmost

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)

result = findBottomLeftValue(root)
print(result)  # 输出: 7

[passengersa]

let queue = [root]; let leftmostVal = root.val; // 记录第一层的值 while (queue.length) { let size = queue.length; for (let i = 0; i < size; i++) { let node = queue.shift(); if (i === 0) { // 第一个节点 leftmostVal = node.val; } if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } return leftmostVal;

[RanDong22]

var findBottomLeftValue = function(root) {
    const dfs = (root, height) => {
        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;
};

[MetSystem]

public int FindBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int res = 0;
    while (queue.Count > 0) {
        int size = queue.Count;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.Dequeue();
            if (i == 0) { // 记录每层最左边的节点
                res = node.val;
            }
            if (node.right != null) {
                queue.Enqueue(node.right);
            }
            if (node.left != null) {
                queue.Enqueue(node.left);
            }
        }
    }
    return res;
}

[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为二叉树的节点

[Fuku-L]

代码

/**
 * 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> 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;
    }
}

[RestlessBreeze]

code

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

[yzhyzhyzh123]

代码

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

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

[SunStrongChina]

思路，BFS

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

时间复杂度:O(n)

空间复杂度:O(h)

[yetfan]

代码

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

[catkathy]

Code

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

[wzbwzt]

/* 思路： BFS 广度优先搜索:创建队列，放入待处理节点，创建数组记录已处理节点

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

*/

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

func findBottomLeftValue(root *TreeNode) int {
    var out int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        out = queue[0].Val

        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]

            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
    }

    return out

}

/* 思路： DFS 深度优先搜索: 它从起始节点开始，沿着一条路径尽可能深地探索，直到到达最深处或无法继续前进时回溯，然后继续探索其他路径。DFS 可以用递归或栈来实现。

复杂度： 时间复杂度： O(N), N 为树的节点数 空间复杂度： O(h), h 为树的高度

*/

// Definition for a binary tree node.

func findBottomLeftValue2(root *TreeNode) int {
    var maxdepth int
    var out int = root.Val

    dfs(root, 0, &out, &maxdepth)

    return out

}

func dfs(node *TreeNode, depth int, out *int, maxdepth *int) {
    if node == nil {
        return
    }

    if depth > *maxdepth {
        *out = node.Val
        *maxdepth = depth
    }

    dfs(node.Left, depth+1, out, maxdepth)
    dfs(node.Right, depth+1, out, maxdepth)

}

[954545647]

bfs 和 dfs

/**
 * 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 queue = [root];
  let val = root.val;
  while (queue.length) {
    let len = queue.length;
    while (len) {
      const cur = queue.shift();
      if (cur.right) {
        queue.push(cur.right);
        val = cur.right.val;
      }
      if (cur.left) {
        queue.push(cur.left);
        val = cur.left.val;
      }
      len--;
    }
  }
  return val
};

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

[Moin-Jer]

class Solution {
    int maxDepth = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return map.get(maxDepth);
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        dfs(node.left, level + 1);
        if (level > maxDepth && !map.containsKey(level)) {
            map.put(level, node.val);
            maxDepth = level;
        }
        dfs (node.right, level + 1);
    }
}