leetcode 513. Find Bottom Left Tree Value 最左边的值 + 一个简单的DFS深度优先遍历

柔情只为你懂 2022-06-02 22:50 148阅读 0赞

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

Example 1:  
Input:

2
       / \
      1   3

Output:  
1  
Example 2:  
Input:

1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:  
7  
Note: You may assume the tree (i.e., the given root node) is not NULL.

题意很简单，直接做DFS深度优先遍历即可，在遍历的时候作比较即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int findBottomLeftValue(TreeNode* root) 
        {
            if (root == NULL)
                return 0;
    
            int maxDepth = 0 , res = root->val;
            getAll(root,maxDepth,0,res);
            return res;
        }
    
        void getAll(TreeNode* root, int& maxDepth, int depth,int& res)
        {
            if (root == NULL)
                return;
            else
            {
                getAll(root->left,  maxDepth, depth + 1, res);
                getAll(root->right, maxDepth, depth + 1, res);
                if (depth > maxDepth)
                {
                    maxDepth = depth;
                    res = root->val;
                }
                return;
            }
        }
    };