LeetCode513找树左下角的值

Posted on | | Visitors:
Words count in article: 496 字 | Reading time ≈ 2 分

题目链接

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

题解一

  • 层次遍历
  • 求最后一层最左边的结点
  • 我自己想的思路：层次遍历，保存每一层最左侧的结点，直到二叉树遍历结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Problem: LeetCode 513
// URL: https://leetcode-cn.com/problems/find-bottom-left-tree-value/
// Tags: Tree Queue BFS
// Difficulty: Medium

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
public:
    // 求最后一层最左边的结点
    int findBottomLeftValue(TreeNode* root) {
        // 空树，题目已说明树不会为空
        if (root==nullptr) return 0;
        // 存储当前层中的结点
        queue<TreeNode*> parentNodes;
        parentNodes.push(root);
        // 按层遍历并保存每一层的第一个结点
        TreeNode* leftBottomNode;
        while(!parentNodes.empty()){
            queue<TreeNode*> childNodes;
            // 更新左下角结点指针
            leftBottomNode = parentNodes.front();
            // 获取下一层结点
            while(!parentNodes.empty()){
                root = parentNodes.front();
                parentNodes.pop();
                if (root->left!=nullptr) childNodes.push(root->left);
                if (root->right!=nullptr) childNodes.push(root->right);
            }
            // 更新当前层
            parentNodes = childNodes;
        }
        return leftBottomNode->val;
    }
};

题解二

  • 其他人的思路
  • 也是按层遍历，但是会先遍历右子结点再遍历左子结点，这样遍历二叉树时最后一个结点就是最后一层最左侧的结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Problem: LeetCode 513
// URL: https://leetcode-cn.com/problems/find-bottom-left-tree-value/
// Tags: Tree Queue BFS
// Difficulty: Medium

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
public:
    // 求最后一层最左边的结点
    int findBottomLeftValue(TreeNode* root) {
        // 存储当前层中的结点
        queue<TreeNode*> nodes;
        nodes.push(root);
        // 按层遍历，但先遍历右子结点再遍历左子结点
        while(!nodes.empty()){
            root = nodes.front();
            nodes.pop();
            if (root->right!=nullptr) nodes.push(root->right);
            if (root->left!=nullptr) nodes.push(root->left);
        }
        return root->val;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!