Leetcode 513. 找树左下角的值

原题链接：Leetcode 513. Find Bottom Left Tree Value

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

Input: root = [2,1,3]
Output: 1

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

Constraints:

• The number of nodes in the tree is in the range [1, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

---

做法一：dfs

思路：

用两个变量记录当前的节点值以及当前节点的最大高度。
每往下一层高度加一，并递归左右子树。（有限递归左子树能保证在同一高度情况下答案一定是最左边的）
如果高度超过了记录的高度，就更新节点值以及最大高度

c++代码：

/** * 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:
    void dfs(TreeNode* root, int height, int &ans, int &maxHeight){
    
            if(root == nullptr)
                return;
            
            // 到下一层, 先递归左孩子, 再递归右孩子
            height++;
            dfs(root->left, height, ans, maxHeight);
            dfs(root->right, height, cuansrVal, maxHeight);

            // 当高度比最大高度还大时, 更新
            if(height > maxHeight){
    
                ans = root->val;
                maxHeight = height;
            }
        }

    int findBottomLeftValue(TreeNode* root) {
    
        // ans为最底层最左边的节点值 maxHeight为最大深度
        int ans, maxHeight = 0;
        dfs(root, 0, ans, maxHeight);

        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(n)，会遍历每一个节点
• 空间复杂度：O(n)，当所有节点都在一边时，递归栈的最大深度就是n