【翻转二叉树】LeetCode 226. Invert Binary Tree

文章目录

• 题目描述
• 知识点
• 结果
• 实现
• 码前思考
• 代码实现
• 码后反思

题目描述

知识点

树

结果

实现

码前思考

1. 树的很多操作都是递归操作左右子树实现的。。。
2. 因此，采用递归的方式翻转二叉树，体现一种自顶向下，再自底向上的思想。

代码实现

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
//树的操作，很多都是使用递归进行的~递归左右子树~
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == NULL){return root;}else{invertTree(root->left);invertTree(root->right);swap(root->left,root->right);return root;}}
};

码后反思

1. 也可以使用层序遍历进行解题，也就是迭代的方式，而不是递归~：

   import java.util.LinkedList;
   import java.util.Queue;public class Solution {public TreeNode invertTree(TreeNode root) {// 结点为空的特殊情况要先考虑if (root == null) {return null;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode curNode = queue.poll();// 只要其中之一非空，我都交换，并且把非空的结点添加到队列里if (curNode.left != null || curNode.right != null) {// 先翻转TreeNode temp = curNode.left;curNode.left = curNode.right;curNode.right = temp;// 把非空的节点加入队列if (curNode.left != null) {queue.offer(curNode.left);}if (curNode.right != null) {queue.offer(curNode.right);}}}return root;}
   }