给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0≤n≤15000 ,树上每个节点的val满足 ∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)
例如：
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
思路：用队列层次遍历， 最后打印时将偶数行反转
class Solution {
public:
vector > Print(TreeNode* pRoot) {
int a=-1;
vector> line;
if(pRoot==NULL)
return line;
queue q;
q.push(pRoot);
while(!q.empty()){
a++;
vector temp ;
line.push_back(temp);
int l=q.size();
while(l!=0) {
line[a].push_back(q.front()->val);
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();
l--;
}
}
for(int i=0;i
重点：
1. 一开始犯了一个错误，是在层次遍历时按照奇数行和偶数行进行反转了，导致每个结点的左右孩子是反转的，但是结点与结点之间的孩子的顺序不一致。例如1，2，3，4变成了3，4，1，2
2.交换vector容器中元素的顺序可以用reverse函数
vector v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值为1,2,3,4,5
3. 不用把调整偶数行顺序单独拿出来再遍历一遍，可以在层次遍历中就使用reverse。
参考他人代码：
class Solution {
public:
vector > Print(TreeNode* pRoot) {
vector> ret;
if (!pRoot) return ret;
queue q;
q.push(pRoot);
int level = 0;
while (!q.empty()) {
int sz = q.size();
vector ans;
while (sz--) {
TreeNode *node = q.front();
q.pop();
ans.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
++level;
if (!(level&1)) // 偶数层 反转一下
reverse(ans.begin(), ans.end());
ret.push_back(ans);
}
return ret;
}
};
描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤10000 −1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
思路：两个结点p1,p2分别遍历两个链表，数值较小的结点加入新的链表，向后移动一个结点，直至其中一个链表走到末尾。如果仍有结点剩下，只可能是其中一个链表p1或p2，新的链表直接加上剩余链表即可。
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* pHead3=(ListNode*)malloc(sizeof(ListNode));
ListNode* p1=pHead1;
ListNode* p2=pHead2;
ListNode* p3=pHead3;
while(p1&&p2){
if(p1->val<=p2->val){
p3->next=p1;
p1=p1->next;
}
else{
p3->next=p2;
p2=p2->next;
}
p3=p3->next;
}
p3->next=p1?p1:p2;
return pHead3->next;
}
};
重点：
1. 题目没有明确说明是否包含头结点，比较迷惑。从结果推条件，应该是两个链表都没有头结点，只有头指针。但在做题时为了方便自己设置了一个头结点，返回头结点后一个指针。
2. 第一次书写的时候将两个链表是否为空的可能性都列出来了，考虑的比较复杂。
3.学着多试着运用三元表达式，还不太熟练。
描述
给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
1.返回第k小的节点值即可
2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3.保证n个节点的值不一样
数据范围： 0≤n≤10000，0≤k≤10000 ，树上每个结点的值满足0≤val≤10000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
思路：用中序遍历，且记下左子树结点个数，若个数+1为k则返回父结点的值
public:
int count=0;//左子树结点加1
int result=-1;//返回值
int KthNode(TreeNode* proot, int k) {
if(proot==NULL||k<=0)
return -1;
KthNode(proot->left,k);
++count;
if(count==k) return result=proot->val;
KthNode(proot->right,k);
return result;
}
};
