代码随想录算法训练营第十六天| 找树左下角的值路径总和从中序与后序遍历序列构造二叉树 -526互联

找树左下角的值

1，层序遍历，较为简单：

 1 int findBottomLeftValue_simple(TreeNode* root) {
 2     int result = 0;
 3     if (!root) return result;
 4     queue<TreeNode*> selected;
 5     selected.push(root);
 6     
 7     while (!selected.empty())
 8     {
 9         int i = selected.size();
10         result = selected.front()->val;
11         while (i != 0)
12         {
13             auto cur_ = selected.front();
14             selected.pop();
15 
16             if (cur_->left) selected.push(cur_->left);
17             if (cur_->right) selected.push(cur_->right);
18             i--;
19         }
20     }
21     return result;
22 }

2，递归法：

注意：终止条件是叶子节点，如果是叶子节点，就判断他是不是最大的深度，如果是，那么就更新它的值

而且需要先左后右，这样就不会导致被替换

代码：

 1 void findBottom_cur(TreeNode* node, int &height, int& maxHeight, int& result)
 2 {
 3     if (!node) return ;
 4 
 5 
 6     //获得左叶子的值，需要判断它是否是最底层
 7     if (!node->left && !node->right)
 8     {
 9         if (height > maxHeight)
10         {
11             result = node->val;
12             maxHeight = height;
13         }
14             
15         return;
16     }
17 
18     height += 1;
19     findBottom_cur(node->left, height, maxHeight, result);
20     height -= 1;
21     height += 1;
22     findBottom_cur(node->right, height,maxHeight, result);
23     height -= 1;
24 
25 }
26 int findBottomLeftValue(TreeNode* root) {
27     int result = 0;
28     int height = 0;
29     int maxHeight = INT_MIN;
30     findBottom_cur(root, height, maxHeight, result);
31     return result;;
32 }