二叉树的蛇形遍历 leetcode 103

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

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

首先我们想一下二叉树的层序遍历的思想：

层序遍历的主要思路就是先把根节点存入，然后输出，输出的同时把根节点的左右孩子存入，再把左孩子输出，同样输出的同时把左孩子的孩子在存入，直到遍历完成，例如：

      a

  b       c

d   e   f   g   

先把a存入，然后输出a，输出a的同时把b c存入，然后再输出b,输出b的同时存入d e，继续输出c，然后存入f g，直到全部输出

//层序遍历
vector<int> levelOrder(TreeNode *root) {
	vector<int> answer;
	queue<TreeNode *>p;
	if (root == nullptr) return answer;
	p.push(root);
	TreeNode* h = nullptr;
	while (!p.empty()) {
		int size = p.size();
		while (size--) {
			h = p.front();
			answer.push_back(h->val);
			p.pop();
			//子树非空，则压入队列   
			if (h->left != NULL)
				p.push(h->left);
			if (h->right != NULL)
				p.push(h->right);
		}
	}
	return answer;

}

思路一：对特定输入的结果进行反转输出

因为输出结果是第二层、第四层、第六层。。。的层序遍历结果反向输出，可以在输出时将对应的行反转输出即可。

//蛇形遍历(反转)
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	vector<vector<int>> answer;
	if (root == nullptr) return answer;

	queue<TreeNode *>p;
	p.push(root);
	TreeNode* h = nullptr;

	while (!p.empty()) {
		int size = p.size();
		vector<int> temp;
		while (size--) {
			h = p.front();
			temp.push_back(h->val);
			p.pop();
			//子树非空，则压入队列   
			if (h->left != NULL)
				p.push(h->left);
			if (h->right != NULL)
				p.push(h->right);
		}
		answer.push_back(temp);
	}

	for (int i = 1; i < answer.size(); i += 2) {
		reverse(answer[i].begin(), answer[i].end());
	}

	return answer;
}

思路二：利用双端队列

//蛇形遍历（双端队列）
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	vector<vector<int>> answer;
	if (root == nullptr) return answer;

	deque<TreeNode*> deq;
	deq.push_back(root);
	int flag = 0;
	int size = 1;
	TreeNode *node = nullptr;

	while (!deq.empty()) {
		vector<int> vec;
		size = deq.size();
		for (int i = 0; i < size; i++) {
			node = deq.front();
			deq.pop_front();
			//从左到右      
			if (flag % 2 == 0) {
				vec.push_back(node->val);
			}
			else {
				vec.insert(vec.begin(), node->val);
			}
			if (node->left != NULL)
				deq.push_back(node->left);
			if (node->right != NULL)
				deq.push_back(node->right);
		}
		answer.push_back(vec);
		flag++;
	}
	return answer;
}

研究了一下双端队列，后来发现改成队列就可以了。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {  
    vector<vector<int>> answer;  
    if (root == nullptr) return answer;  
  
    queue<TreeNode*> deq;  
    deq.push(root);  
    int flag = 0;  
    int size = 1;  
    TreeNode *node = nullptr;  
  
    while (!deq.empty()) {  
        vector<int> vec;  
        size = deq.size();  
        for (int i = 0; i < size; i++) {  
            node = deq.front();  
            deq.pop();  
            //从左到右        
            if (flag % 2 == 0) {  
                vec.push_back(node->val);  
            }  
            else {  
                vec.insert(vec.begin(), node->val);  
            }  
            if (node->left != NULL)  
                deq.push(node->left);  
            if (node->right != NULL)  
                deq.push(node->right);  
        }  
        answer.push_back(vec);  
        flag++;  
    }  
    return answer;  
}  
};