leetcode简单题6

发表于   |   分类于   |  

今天的华师

1

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

return its bottom-up level order traversal as:

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

思路：

树的层次遍历，技巧是用NULL作为每一行的结尾
问题是什么时候才能是结尾呢？
当遇到队列中front是NULL时，表明上一行已经处理完了，则上一行的子节点也处理完了（处理每个节点的时候，让他的孩子节点入队列），此时把NULL加入队列
当队列中只有一个NULL的时候，则遍历完毕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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>> levelOrderBottom(TreeNode* root) {
		vector<vector<int>> result;
		if (root == NULL)
			return result;
		vector<int> line;
		queue<TreeNode*> Q;
		Q.push(root);
		Q.push(NULL);
		while (Q.size()>1)
		{
			TreeNode *p = Q.front();
			Q.pop();
			if (p == NULL)
			{
				result.push_back(line);
				line.clear();
				Q.push(NULL);
			}
			else
			{
				line.push_back(p->val);
				if (p->left != NULL)
				{
					Q.push(p->left);
				}
				if (p->right != NULL)
				{
					Q.push(p->right);
				}
			}
		}
		result.push_back(line);
		reverse(result.begin(), result.end());
		return result;
	}
};

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        reverse(digits.begin(),digits.end());
        int len=digits.size();
        int carry=1;
        for(int i=0;i<len;i++)
        {
            int temp=digits[i]+carry;
            if(temp==10)
            {
                digits[i]=0;
                carry=1;
            }
            else
            {
                digits[i]=temp;
                carry=0;
            }
        }
        if(carry==1)
        digits.push_back(1);
        reverse(digits.begin(),digits.end());
        return digits;
    }
};