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

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

news 2025/4/28 10:15:55

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

#include <iostream>
#include <climits>
#include <sstream>
#define LEN 10009struct 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));elsetnArr[index] = nullptr;if (index > 0) {if (index % 2 == 1)tnArr[index / 2]->left = tnArr[index];elsetnArr[(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;
}