专栏首页流川疯编写程序的艺术leetcode 102 Binary Tree Level Order Traversal

leetcode 102 Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

我的解决方案,非常传统的两个队列的解决方案:

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        
      
	vector<vector<int>> result;
	queue<TreeNode*> q;

	if (root == NULL)
	{
		return result;
	}
	q.push(root);
	vector<int> le_temp;

	while(!q.empty())
	{

		le_temp.clear();
		queue<TreeNode*> level;
            
        int size = q.size();    
		for(int i = 0; i < size; ++i)
		{
			TreeNode* temp = q.front();
			q.pop();
			if(temp->left)
			{
				level.push(temp->left);
			}
			if(temp->right)
			{
				level.push(temp->right);
				
			}
			le_temp.push_back(temp->val);
		}

		while(!level.empty())
		{

			q.push(level.front());   
			level.pop();
		}
		result.push_back(le_temp);
	}

	return result;
        
    }
};

一个栈似乎也行:

 vector<vector<int>> levelOrder(TreeNode* root) 
    {
        
     vector<vector<int> >  result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> cur_vec;
        while(!q.empty()) {
            TreeNode* t = q.front();
            q.pop();
            if (t==NULL) {
                result.push_back(cur_vec);
                cur_vec.resize(0);
                if (q.size() > 0) {
                    q.push(NULL);
                }
            } else {
                cur_vec.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return result;

        
    }

递归的解决方案:

class Solution {
public:
    vector<vector<int>> result;
    void buildVector(TreeNode* root, int depth)
    {
        if(root == NULL)return ;
        if(result.size() == depth)
        {
            result.push_back(vector<int>());
        }
        
        result[depth].push_back(root->val);
        
        buildVector(root->left,depth + 1);
        buildVector(root->right, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        buildVector(root,0);
        return result;
    }
};

逆序排列把return 改一下就好了:  return vector<vector<int> > (result.rbegin(), result.rend()); }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode 104 Maximum Depth of Binary Tree二叉树求深度

    Maximum Depth of Binary Tree Total Accepted: 63668 Total Submissions: 141121 ...

    用户1539362
  • OpenCV导向滤波(引导滤波)实现(Guided Filter)代码,以及使用颜色先验算法去雾

     论文下载地址:http://research.microsoft.com/en-us/um/people/jiansun/papers/GuidedFilte...

    用户1539362
  • leetcode 生成杨辉三角形, 118 119 Pascal's Triangle 1,2

    Given numRows, generate the first numRows of Pascal's triangle.

    用户1539362
  • 【畅通工程 HDU - 1232 】【并查集模板题】

    话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲...

    _DIY
  • 3n+1问题

    猜想:对于任意大于1的自然数n,若n为奇数,则将n变为3n+1,否则变为n的一半。

    Vincent-yuan
  • 基于AES加密的RTSP/RTMP多路转发设计方案

    很多开发者跟我们探讨,除了Windows推送端采集编码的音视频数据可以加密外,其他RTSP/RTMP流如果想更安全的转推到RTMP服务器或相应CDN改怎么办?

    daniulive
  • HashMap源码理解

    private static int roundUpToPowerOf2(int number) {     return number >= MAXIMUM_...

    MonroeCode
  • 【死磕Java并发】—–J.U.C之并发工具类:Semaphore

    信号量Semaphore是一个控制访问多个共享资源的计数器,和CountDownLatch一样,其本质上是一个“共享锁”。

    用户1655470
  • webkit和blink在blob机制上不同的地方

    WebKit.dll!WebCore::BlobURL::createBlobURL(const WTF::String & originString...

    龙泉寺扫地僧
  • 【死磕Java并发】—– J.U.C之并发工具类:Semaphore

    芋道源码

扫码关注云+社区

领取腾讯云代金券