binary-tree-zigzag-level-order-traversal

题目描述

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

题解

dfs，对应层判断一下奇偶，决定在表头还是表尾添加元素就可以了

void dfs2(TreeNode* root,int depth, vector<vector<int>>& res)
{
	if (!root)return;
	if (res.size() <= depth)
		res.push_back({ root->val });
	else
	{
		if (depth % 2)
		{//由右向左扫描，从首部压入
			res[depth].insert(res[depth].begin(), root->val);
		}
		else
		{//由左向右扫描，从尾部加入
			res[depth].push_back(root->val);
		}
	}
	dfs2(root->left, depth + 1, res);
	dfs2(root->right, depth + 1, res);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	if (!root)return {};
	vector<vector<int>> res = {};
	dfs2(root, 0, res);
	return res;
}

执行用时 :4 ms, 在所有 C++ 提交中击败了81.94%的用户

内存消耗 :12.1 MB, 在所有 C++ 提交中击败了100.00%的用户

附加一个小虾米

int maxDepth(TreeNode* root) {
	if (!root)return 0;
	return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}