当前位置：首页 > article >正文

代码随想录算法训练营第十六天-二叉树-513.找树左下角的值

article 2025/1/1 14:33:17

左下角不是以为的左下角，而最后一层最左侧的节点
也是就是说一个右叶子节点，也可能是最左下角，当然是在其左侧再无其它同级节点
看视频讲解使用的递归与回溯方法，自己是完全想不到的，对这道题解法完全是脑袋空空

#include <iostream>
#include <climits>
#include <sstream>
#define LEN 10009

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
    TreeNode(int v, TreeNode* l, TreeNode* r): val(v), left(l), right(r) {}
};

class Solution {
private:
    int max_depth = INT_MIN;
    int bottomLeftValue;
public:
    TreeNode* getTree() {
        // TreeNode* tnArr[] = new TreeNode*[LEN];
        TreeNode* tnArr[LEN] {nullptr};
        std::string str_content;
        std::getline(std::cin, str_content);
        std::stringstream ss {str_content};
        for (int index = 0; ss >> str_content; ++index) {
            if (str_content != "null")
                tnArr[index] = new TreeNode(stoi(str_content));
            else
                tnArr[index] = nullptr;
            if (index > 0) {
                if (index % 2 == 1)
                    tnArr[index / 2]->left = tnArr[index];
                else
                    tnArr[(index - 1) / 2]->right = tnArr[index];
            }
        }
        return tnArr[0];
    }
    void traversal(TreeNode* node, int depth) {
        if (node->left == nullptr && node->right == nullptr) {
            if (depth > max_depth) {
                max_depth = depth;
                bottomLeftValue = node->val;
            }
        }
        if (node->left)
            traversal(node->left, depth + 1);
        if (node->right)
            traversal(node->right, depth + 1);
    }
    int findBottomLeftValue(TreeNode* node) {
        traversal(node, 1);
        return bottomLeftValue;
    }
};
int main()
{
    Solution s;
    TreeNode* root = s.getTree();
    std::cout << "******" << std::endl;
    std::cout << s.findBottomLeftValue(root) << std::endl;
    return 0;
}