力扣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;
}

原文地址：https://blog.csdn.net/m0_56332819/article/details/143748329

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！