LeetCode513. 找树左下角的值

题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/description/

题目叙述：

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:

1. 输入: root = [2,1,3]
2. 输出: 1

复制代码

示例 2:

1. 输入: [1,2,3,4,null,5,6,null,null,7]
2. 输出: 7

复制代码

提示:


二叉树的节点个数的范围是 [1,10^4]
-2^31 right==NULL){            if(depth>maxdepth){                maxdepth=depth;                result=cur->val;            }            return;        }[/code]单层递归的逻辑

我们现在找到了最深层次的叶子节点，那么我们如何包管它一定是最左边的节点呢？那还不简朴嘛！只必要我们处理递归的时候，优先处理左子树，不就能包管我们先处理的是左孩子了嘛！对吧，
这段逻辑的代码如下：

1.        //处理到叶子节点就返回
2.         if(cur->left==NULL&&cur->right==NULL){
3.             if(depth>maxdepth){
4.                 maxdepth=depth;
5.                 result=cur->val;
6.             }
7.             return;
8.         }

复制代码

其实，处理好了这几个界限条件，我们的代码就出来了
整体代码：

1. class Solution {public:    int result=0;    int maxdepth=INT_MIN;    void traversal(TreeNode*cur,int depth){        //处理到叶子节点就返回        if(cur->left==NULL&&cur->right==NULL){            if(depth>maxdepth){                maxdepth=depth;                result=cur->val;            }            return;        }       //处理到叶子节点就返回
2.         if(cur->left==NULL&&cur->right==NULL){
3.             if(depth>maxdepth){
4.                 maxdepth=depth;
5.                 result=cur->val;
6.             }
7.             return;
8.         }    }    int findBottomLeftValue(TreeNode* root) {        traversal(root,0);        return result;    }};

复制代码

层序遍历（迭代法）

其实，这题使用层序遍历才是最方便，最简朴的做法。我们只必要处理每一层的第一个元素，然后处理到末了一层，它自然就是末了一层的左边第一个元素了，这题只必要在层序遍历的模板上面改动一点点
就可以实现了！
假如不会层序遍历的话，推荐去看看我的层序遍历的文章，内里详细讲授了层序遍历实现的过程！
层序遍历：https://www.cnblogs.com/Tomorrowland/p/18318744

1. class Solution {
2. public:
3.     int result=0;
4.     int maxdepth=INT_MIN;
5.     void traversal(TreeNode*cur,int depth){
6.         //处理到叶子节点就返回
7.         if(cur->left==NULL&&cur->right==NULL){
8.             if(depth>maxdepth){
9.                 maxdepth=depth;
10.                 result=cur->val;
11.             }
12.             return;
13.         }
14.             if(cur->left!=NULL){
15.             //先让depth++，让他处理下一层的节点
16.             depth++;
17.             traversal(cur->left,depth);
18.             //再让depth--，这就是回溯的过程，退到上一层的节点，再处理右边的子树
19.             depth--;
20.         }
21.             if(cur->right!=NULL){
22.             //这里也是一样的道理
23.             depth++;
24.             traversal(cur->right,depth);
25.             //这里也是回溯的过程
26.             depth--;
27.         }
28.     }
29.     int findBottomLeftValue(TreeNode* root) {
30.         traversal(root,0);
31.         return result;
32.     }
33. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。