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

[zhiyuanpeng]

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

time O(N) space(logN)

[wwz223]

思路

采用深度遍历的方式，从右子节点开始深度遍历，记录left值和maxDeep的值，采用从右往左的方式的目的是为了遍历同一层级的时候左节点值可以对右节点值进行覆盖，这里的核心逻辑就是判断当前deep是否大于等于maxDeep，如果大于则代表是更深的一层，所以对left进行一个重新赋值

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    let left = root.val; 
    let maxDeep = 0;
    const order = (node, deep) => {
        if(!node || node.val === null) return 
        if(deep >= maxDeep){
            maxDeep = deep
            left = node.val
        }
        order(node.right, deep + 1);
        order(node.left, deep + 1);
    }
    order(root,1)
    return left
};

复杂度分析

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

[luzhaofeng]

class Solution:
    def findValue(self, root):
        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

[CathyShang]

思路： BFS，遍历到最后一层，返回首元素。

代码：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(root->left == nullptr && root->right==nullptr) return root->val;
        queue<TreeNode*> q;
        q.push(root);
        int res;
        while(!q.empty()){
            TreeNode* node;// 拿出首个元素
            queue<TreeNode*> tmp;
            int n = q.size();
            for(int i=0;i<n; i++){
            node = q.front();
            q.pop();
            if(node->left!=nullptr) tmp.push(node->left);
            if(node->right!=nullptr) tmp.push(node->right);
            }
            q=tmp;
            if(q.empty()) break; // for出来最后一次为空
            res = tmp.front()->val;
        }
        return res;

    }
};

复杂度：

• 时间 $O(N)$ 树节点数
• 复杂 $O(Q)$ 树的宽度

[lxy1108]

思路

bfs层次遍历树，返回最后一层最左侧的节点

python3代码

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

复杂度分析

时间复杂度o(n) 需要遍历所有节点

空间复杂度o(n) 维护队列存储每层节点

[xil324]

/**

• @param {TreeNode} root
• @return {number} */ var findBottomLeftValue = function(root) { const queue = [], levels = []; queue.push(root); while(queue.length) { const level = [] const queueSize = queue.length; for(let i = 0; i<queueSize; i++) { const node = queue.shift(); level.push(node.val); if(node.left) queue.push(node.left); if(node.right) queue.push(node.right); } levels.push(level) } return levels[levels.length-1][0]

};

[smallppgirl]

思路： 广度优先搜索(BFS), 利用deque 代码

    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

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

[GReyQT]

题解思路：

（1）层序遍历树，且先把右节点入队，再把左节点入队，最有一个节点就是左下角节点；

代码：

/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        if (root == nullptr)
            return 0; // 如果根节点为空，直接返回
        queue<TreeNode*> q;
        q.push(root); // 将根节点入队
        while (!q.empty()) {
            TreeNode* current = q.front(); // 获取队列头部节点
            q.pop(); // 将头部节点出队
            // 如果有右子节点，将右子节点入队
            if (current->right != nullptr) {
                q.push(current->right);
            }
            // 如果有左子节点，将左子节点入队
            if (current->left != nullptr) {
                q.push(current->left);
            }
        }
        return q.back()->val;
    }
};

复杂度分析：

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

[Dtjk]

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

[atom-set]

思路

• 求解在树的最后一行找到最左边的值，要借助 BFS 思想
• 这里有个小技巧，在 BFS 遍历过程中，先访问右节点，再访问左节点，可以确定最后访问的叶子节点就是想要的结果

代码

var findBottomLeftValue = function (root) {
  if (!root) {
    return -1;
  }

  var dist = root;
  var queue = [];
  queue.push(root);
  var flag = 0;
  while (queue.length > 0) {
    var point = queue.shift();
    if (point.right) {
      dist = point.right;
      queue.push(point.right);
    }
    if (point.left) {
      dist = point.left;
      queue.push(point.left);
    }
  }
  return dist.val;
};

复杂度分析

递归需要遍历每个节点，故时间复杂度为 O(N) 递归调用的深度和树的高度有关，故空间复杂度为 O(H)

• 时间复杂度: O(N)
• 空间复杂度: O(H)

[hillsonziqiu]

思路

深度优先，优先遍历左边节点。

代码

/**
 * 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)
 * }
 */
const dfs = (root, h, callback) => {
    if (!root) return;

    h++;
    dfs(root.left, h, callback);
    dfs(root.right, h, callback);

    callback && callback(h, root.val);
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let [height, val] = [0, undefined];

    dfs(root, 0, (h, curVal) => {
        if (h > height) {
            height = h;
            val = curVal;
        }
    })

    return val;
};

复杂度分析

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

[YANGLimbo]

class Solution {
    protected:
    int _value;
    int _depth = -1;
public:
    void preorderTraverse(TreeNode*root, int depth){

        if(depth > _depth){
            _value = root->val;
            _depth = depth;
        }
        if(root->left != nullptr){
            preorderTraverse(root->left, depth +1);
        }
        if(root->right != nullptr){
            preorderTraverse(root->right, depth +1);
        }

    }

    int findBottomLeftValue(TreeNode* root) {
        // 前序遍历，先遍历左子树再找右子树，，这样一来顺序就一定是从左到右
        // 最终的结果不一定是左子叶节点也可能是右
        // 从左到右的过程中比较叶节点的深度，如果深度>之前的进行替换，否则不替换
        preorderTraverse(root, 0);
        return _value;
    }
};