小鲸鱼的梦境
0%

『LeetCode』513 找树左下角的值

发表于 分类于 Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目

513. 找树左下角的值

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

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

示例 1:

tree1

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

示例 2:

tree2

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

提示:

  • 二叉树的节点个数的范围是 \([1,10^{4}]\)
  • \(-2^{31} <= Node.val <= 2^{31} - 1\)

标签

树, 深度优先搜索, 广度优先搜索, 二叉树

题解

【找树左下角的值】常规二叉树遍历の『DFS』&『BFS』

二叉树的搜索

要求找最深最左边的结点，可以使用常规二叉树遍历的深度优先搜索或广度优先搜索方法。

  • 深度优先搜索：按照先左后右的顺序遍历子树，最先搜索到的最深的结点即所求的结点
  • 广度优先搜索：分层搜索，每层记录最左边的结点，最深一层记录的即所求结点

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Code language: Python
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        ans, h = 0, 0

        def dfs(root, height):
            if root:
                nonlocal ans, h
                if height > h:
                    ans, h = root.val, height
                if root.left: dfs(root.left, height + 1)
                if root.right: dfs(root.right, height + 1)
        
        dfs(root, 1)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Code language: Java
class Solution {
    int h = 0, val = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return val;
    }

    public void dfs(TreeNode root, int height) {
        if (root != null) {
            if (height > h) {
                h = height;
                val = root.val;
            }
            dfs(root.left, height + 1);
            dfs(root.right, height + 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Code language: C++
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = 0, h = 0;
        function<void(TreeNode*, int)> dfs = [&ans, &h, &dfs](TreeNode* root, int height) {
            if (root != nullptr) {
                if (h < height) {
                    ans = root->val;
                    h = height;
                }
                if (root->left != nullptr) dfs(root->left, height + 1);
                if (root->right != nullptr) dfs(root->right, height + 1);
            }
        };
        dfs(root, 1);
        return ans;
    }
};

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Code language: Python
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        ans = 0
        st = collections.deque([root])
        while st:
            ans = st[0].val
            # 注意这里 len(st) 只在创建 range 迭代器的时候进行唯一一次传参
            # 循环中不会传参也不会更新 range 迭代器的终点值
            for _ in range(len(st)):
                cur = st.popleft()
                if cur.left: st.append(cur.left)
                if cur.right: st.append(cur.right)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Code language: Java
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        if (root != null) st.add(root);
        int ans = 0;
        while (!st.isEmpty()) {
            ans = st.peekFirst().val;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode cur = st.pollFirst();
                if (cur.left != null)
                    st.addLast(cur.left);
                if (cur.right != null)
                    st.addLast(cur.right);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Code language: C++
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> st;
        if (root != nullptr) st.push(root);
        int ans = 0;
        while (!st.empty()) {
            ans = st.front()->val;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode* cur = st.front();
                st.pop();
                if (cur->left != nullptr)
                    st.push(cur->left);
                if (cur->right != nullptr)
                    st.push(cur->right);
            }
        }
        return ans;
    }
};
  • 时间复杂度: \(O(n)\)，需要遍历整棵树
  • 空间复杂度: \(O(n)\)，栈或队列的开销

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~