513. Find Bottom Left Tree Value（python+cpp）-白红宇

513. Find Bottom Left Tree Value（python+cpp）

阅读量：3705 次

发布时间：2019-05-21

本文共 3220 字，大约阅读时间需要 10 分钟。

题目：

Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:    2       / \     1   3Output: 1
Example 2:
Input:        1       / \      2   3     /   / \    4   5   6       /      7Output: 7
Note: You may assume the tree (i.e., the given root node) is not NULL.

解释：

返回二叉树的最底层的最左边的元素的值。

解法1：

bfs与层序遍历类似

解法2：

right 2 left bfs 返回最后一个结点的val，和解法1本质上还是一样的

解法1，python代码：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def findBottomLeftValue(self, root):        """        :type root: TreeNode        :rtype: int        """        queue=[]        queue.append(root)        ans=0        while queue:            layer_number=len(queue)            for i in xrange(layer_number):                node=queue.pop(0)                if i==0:                    ans=node.val                if node.left:                    queue.append(node.left)                if node.right:                    queue.append(node.right)        return ans

c++代码：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */#include
   
    using namespace std;class Solution {
   public:    int findBottomLeftValue(TreeNode* root) {
           queue
    
     _queue;        _queue.push(root);        TreeNode* node=NULL;        while (!_queue.empty())        {
               int _len=_queue.size();            for (int i=0;i<_len;i++)            {
                   TreeNode* tmp=_queue.front();                _queue.pop();                if(i==0)                    node=tmp;                if(tmp->left)                    _queue.push(tmp->left);                if(tmp->right)                    _queue.push(tmp->right);            }        }        return node->val;    }};

解法2，python代码：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def findBottomLeftValue(self, root):        """        :type root: TreeNode        :rtype: int        """        queue=[]        queue.append(root)        node=None        while queue:            node=queue.pop(0)            if node.right!=None:                queue.append(node.right)            if node.left!=None:                queue.append(node.left)        return node.val

c++代码：

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

总结：

转载地址：http://aglcn.baihongyu.com/

你可能感兴趣的文章

Tomcat 容器与servlet的交互原理