513. 找树左下角的值#

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) :
10
        val(x), left(left), right(right) {}
11
 * };
12
 */
13
class Solution {
14
public:
15
    /* int findBottomLeftValue(TreeNode* root) {
16
        queue<TreeNode* > q;
17
        if(root != NULL) q.push(root);
18
        int result = 0;
19
        while (!q.empty())
20
        {
21
            int n = q.size();
22
            for (int i = 0; i < n; i++)
23
            {
24
                TreeNode* node = q.front();
25
                q.pop();
26
                if(i == 0) result = node->val;
27
                if(node -> left != nullptr) q.push(node -> left);
28
                if(node -> right != nullptr) q.push(node -> right);
29
            }
30
        }
31
        return result; */
32
        int len = INT_MIN;
33
        int value;
34
        void dfs(TreeNode* root, int deep)
35
        {
36
            if(root != nullptr)
37
            {
38
                if(root -> left == nullptr && root -> right == nullptr)
39
                {
40
                    if(deep > len)
41
                    {
42
                        len = deep;
43
                        value = root -> val;
44
                    }
45
                    return;
46
                }
47
                dfs(root -> left, deep + 1);
48
                dfs(root -> right, deep + 1);
49
            }
50
            return;
51
        }
52
    int findBottomLeftValue(TreeNode* root)
53
    {
54
        dfs(root, 0);
55
        return value;
56
    }
57
};