leetcode 226. 翻转二叉树

大忽悠爱学习

发布于 2021-11-15 10:51:38

3330

文章被收录于专栏：c++与qt学习c++与qt学习

翻转二叉树题解集合

DFS写法1

思路一个二叉树，怎么才算翻转了？

它的左右子树要交换，并且左右子树内部的所有子树，都要进行左右子树的交换。

每个子树的根节点都说：先交换我的左右子树吧。那么递归就会先压栈压到底。然后才做交换。
即，位于底部的、左右孩子都是 null 的子树，先被翻转。
随着递归向上返回，子树一个个被翻转……整棵树翻转好了。
问题是在递归出栈时解决的。

  class Solution {
  public:
      TreeNode* invertTree(TreeNode* root) 
	  {
		  if (root == nullptr)
			  return nullptr;
		invertTree(root->left);
		invertTree(root->right);
		TreeNode* temp = root->left;
		root->left = root->right;
		root->right = temp;
		  return root;
      }
  };

DFS写法2

递归思路 2

思路变了：先 “做事”——先交换左右子树，它们内部的子树还没翻转——丢给递归去做。
把交换的操作，放在递归子树之前。
问题是在递归压栈前被解决的。

  class Solution {
  public:
      TreeNode* invertTree(TreeNode* root) 
	  {
		  if (root == nullptr)
			  return nullptr;
		  TreeNode* temp = root->left;
		  root->left = root->right;
		  root->right = temp;
		invertTree(root->left);
		invertTree(root->right);
		  return root;
      }
  };

DFS写法3

第三种写法其实本质就是DFS写法1，只不过我们利用了递归函数的返回值而已，也属于自下而上的处理的递归

  class Solution {
  public:
      TreeNode* invertTree(TreeNode* root) 
	  {
		  if (root == nullptr)
			  return nullptr;
		  TreeNode* left = invertTree(root->left);//获取当前左孩子节点
		  TreeNode* right = invertTree(root->right);//获取当前右孩子节点
		  //交换左右孩子节点
		  root->left = right;
		  root->right = left;
		  return root;//返回当前子树的根节点
      }
  };

对DFS写法的总结

复盘总结

两种分别是后序遍历和前序遍历。都是基于DFS，都是先遍历根节点、再遍历左子树、再右子树。

唯一的区别是：

前序遍历：将「处理当前节点」放到「递归左子树」之前。
后序遍历：将「处理当前节点」放到「递归右子树」之后。

这个「处理当前节点」，就是交换左右子树，就是解决问题的代码：

const temp = root.left;
root.left = root.right;
root.right = temp;

递归只是帮你遍历这棵树，核心还是解决问题的代码，递归把它应用到每个子树上，解决每个子问题，最后解决整个问题。
你可以选择将 “做事” 的代码，放到 DFS 过程中的一个合适的时间点，而已。

评论区有人问递归到 null 不知道返回什么： 递归做的事——交换当前root的左右子树，返回root。遍历到 null，它没有子树可交换，返回出这个子树（null）

BFS

用层序遍历的方式去遍历二叉树。

根节点先入列，然后出列，出列就 “做事”，交换它的左右子节点（左右子树）。
并让左右子节点入列，往后，这些子节点出列，也被翻转。
直到队列为空，就遍历完所有的节点，翻转了所有子树。
解决问题的代码放在节点出列时。

 class Solution {
 public:
	 TreeNode* invertTree(TreeNode* root)
	 {
		 if (root ==nullptr) return nullptr;
		 queue<TreeNode*> q;
		 //根节点入队
		 q.push(root);
		 while (!q.empty())
		 {
			 //队头元素出队
			 TreeNode* first=q.front(); 
			 q.pop();
			 //交换左右孩子节点
			 TreeNode* temp = first->left;
			 first->left = first->right;
			 first->right = temp;
			 //将当前根节点的左右孩子入队---不为空才入队
			 //入队的目的是为了待会出队的时候，交换以当前节点为根的子孙的左右孩子节点
			 if (first->left) q.push(first->left);
			 if (first->right) q.push(first->right);
		 }
		 return root;
	 }
 };