Leetcode 513. Find Bottom Left Tree Value

Tyan

发布于 2019-05-25 22:53:35

2920

发布于 2019-05-25 22:53:35

文章被收录于专栏：SnailTyan SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Iterative

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> currentLayer;
        currentLayer.push(root);
        while(!currentLayer.empty()) {
            queue<TreeNode*> nextLayer;
            int val = currentLayer.front()->val;
            while(!currentLayer.empty()) {
                TreeNode* node = currentLayer.front();
                currentLayer.pop();
                if(node->left) {
                    nextLayer.push(node->left);
                }
                if(node->right) {
                    nextLayer.push(node->right);
                }
            }
            if(nextLayer.empty()) {
                    return val;
            }
            currentLayer = nextLayer;
        }
    }
};

Recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> list;
        list.push(root);
        return findValue(list);
    }

    int findValue(queue<TreeNode*> currentLayer) {
        int val = currentLayer.front()->val;
        queue<TreeNode*> nextLayer;
        while(!currentLayer.empty()) {
            TreeNode* node = currentLayer.front();
            currentLayer.pop();
            if(node->left) {
                nextLayer.push(node->left);
            }
            if(node->right) {
                nextLayer.push(node->right);
            }
        }
        if(nextLayer.empty()) {
            return val;
        }
        else {
            return findValue(nextLayer);
        }
    }
};