Day123 | 灵神 | 二叉树 | 找树左下角的值

Day123 | 灵神 | 二叉树 | 找树左下角的值

513.找树左下角的值

513. 找树左下角的值 - 力扣（LeetCode）

思路：

初学者可以看灵神视频二叉树的层序遍历【基础算法精讲 13】_哔哩哔哩_bilibili

我的思路就是在每层的循环前加个判断，把res更新队头元素，队头肯定是最左边的

灵神思路是先入队右孩子再入队左孩子，这样最后一个出队的肯定是最左边的

完整代码：

笔者思路：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> q;
        int res=0;
        if(root==nullptr)
            return res;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int> path;
            for(int i=size;i>0;i--)
            {
                TreeNode *t=q.front();
                q.pop();
                if(i==size)
                    res=t->val;
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
        }
        return res;
    }
};

灵神代码：

class Solution {
public:
    int findBottomLeftValue(TreeNode *root) {
        TreeNode *node;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            node = q.front(); q.pop();
            if (node->right) q.push(node->right);
            if (node->left)  q.push(node->left);
        }
        return node->val;
    }
};

递归写法：

class Solution {
public:
    int res;
    int curdepth=0;
    void tra(TreeNode *t,int depth)
    {
        if(t->left==nullptr&&t->right==nullptr)
        {
            if(depth>curdepth)
            {
                res=t->val;
                curdepth=depth;
            }
            return;
        }
        if(t->left)
            tra(t->left,depth+1);
        if(t->right)
            tra(t->right,depth+1);
    }
    int findBottomLeftValue(TreeNode* root) {
        tra(root,1);
        return res;
    }
};