力扣513:找树左下角的值
给定一个二叉树的 根节点 root
,请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
层层遍历代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#define MAX 10000
int height(struct TreeNode *t){
if(t==NULL) return 0;
int heightl=height(t->left);
int heightr=height(t->right);
return (heightl > heightr ? heightl:heightr)+1;
}
int findBottomLeftValue(struct TreeNode* root) {
if(root==NULL) return 0;
int TReeHeight=height(root);
//利用队列进行层次遍历(BFS)
struct TreeNode *Queue[MAX];
struct TreeNode *temp;
int front=0,rear=0,len=0;
Queue[rear++]=root;
int level=0;
while(front<rear){
len=rear-front;
level++;
for(int i=0;i<len;i++){
if(level==TReeHeight){
return Queue[front]->val;
}
temp=Queue[front++];
if(temp->left!=NULL) Queue[rear++]=temp->left;
if(temp->right!=NULL) Queue[rear++]=temp->right;
}
}
return 0;
}
递归代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int depth;
int temp;
void DFS(struct TreeNode *root,int h){
if(root==NULL) return;
DFS(root->left,h+1);
if(h>depth){
depth=h;
temp=root->val;
}
DFS(root->right,h+1);
}
int findBottomLeftValue(struct TreeNode* root) {
depth=-1,temp=0;
DFS(root,1);
return temp;
}