代码随想录算法训练营第15天 | 二叉树层序遍历 226.翻转二叉树 101.对称二叉树

二叉树层序遍历

这样一层一层地遍历就是广度优先搜索，队列先入先出的性质是最合适的。

class Solution{
public:
	vector<vector<int>> levelOrder(TreeNode* root){
		vector<vector<int>> result;
		if(root == NULL)  return result;
		queue<TreeNode*> que;
		que.push(root);
		while(!que.empty()){
			int size = que.size();  // 此时队列中本层中的节点，记录队列的长度，因为后面还会继续向队列中添加下一层的节点
			vector<int> vec;
			for(int i = 0; i < size; i++){
				TreeNode* node = que.front();
				que.pop();
				vec.push_back(node->val);
				if(node->left)  que.push(node->left);
				if(node->right)  que.push(node->right);
			}
			result.push_back(vec);
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

也可以用递归的方法实现，要注意递归函数的传入参数，因为我们是一层一层遍历的，所以应该传入当前节点的所属层次。不需要返回参数，只需要保存结果数组。

class Solution{
public:
	void traversal(TreeNode* node, vector<vector<int>>& res, int depth){
		if(node == NULL)  return;
		if(res.size() == depth)  res.push_back(vector<int>());  // 如果这一层还没处理，添加这一层的空数组，以便后续添加元素值
		res[depth].push_back(node->val);
		traversal(node->left, res, depth + 1);
		traversal(node->right, res, depth + 1);
	}
	vector<vector<int>> levelOrder(TreeNode* root){
		vector<vector<int>> result;
		traversal(root, result, 0);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

翻转二叉树

所谓翻转二叉树，其实就是将每个节点的左右节点交换一下。那问题就变成了如何遍历每个节点，并翻转每个节点，使用前中后层序哪种遍历呢？其实仔细考虑一下，**中序会导致有些节点被翻转两次，是不能直接使用的。**我们在遍历问题中，处理是把元素值放进结果数组，在翻转中则是交换左右节点。
其实中序也可以使用的，但要修改一下代码。

class Solution{
public:
	TreeNode* invertTree(TreeNode* root){
		if(root == NULL)  return root;
		invertTree(root->left);
		swap(root->left, root->right);
		invertTree(root->left); // 因为中间节点已经被翻转了，右节点已经变成了左节点，所以只有再反转左侧才是在翻转之前的右节点
		return root;
	}
};
1
2
3
4
5
6
7
8
9
10

但是统一迭代法实现的中序遍历是可以直接用的，这是个有趣的现象。因为它是将节点放进了栈中，当元素推出栈时不是翻转后的结果，仍然是原来的节点，这就没问题了。

对称二叉树

递归法

• 确定递归函数的参数和返回值：我们需要比较根节点的两个子树是相互翻转的，所以要比较的是两个树，递归函数的参数是需要比较的两个节点。
• 确定返回条件：这个稍微复杂一些。两个节点都空？一个空一个不空？两个都不空？
• 单层递归的逻辑：左孩子和右孩子比较；右孩子和左孩子比较。

class Solution{
public:
	bool compare(TreeNode* left, TreeNode* right){
		if(!left && !right)  return true;
		else if(left && !right)  return false;
		else if(!left && right)  return false;
		else if(left->val != right->val)  return false;
		
		bool is_left = compare(left->left, right->right);
		bool is_right = compare(left->right, right->left);
		return is_left && is_right;
	}
	bool isSymmetric(TreeNode* root){
		return compare(root->left, root->right);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

迭代法

由于这道题本质上是比较两棵树，并不同于之前的遍历方法。我们用一个额外的容器实现迭代法，可以是栈、队列、数组等等。这个容器的相邻元素放的是要比较的左右节点节点。

class Solution{
public:
	bool isSymmetric(TreeNode* root){
		queue<TreeNode*> que;
		que.push(root->left);
		que.push(root->right);
		while(!que.empty()){
			TreeNode* leftNode = que.front();
			que.pop();
			TreeNode* rightNode = que.front();
			que.pop();
			if(!leftNode && !rightNode){  // 左节点和右节点都是空的
				continue;
			}
			// 如果一个节点空一个节点不空，或者两个节点都不空但元素值不相等
			if(!leftNode || !rightNode || (leftNode->val != rightNode->val)){
				return false;
			}
			que.push(leftNode->left);
			que.push(rightNode->right);  // 外侧节点加入容器
			que.push(leftNode->right);
			que.push(rightNode->left);  // 内侧节点加入容器
		}
		return true;
	}
};
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