二叉树——226. 翻转二叉树

深碍√TFBOYSˉ_ 2023-10-08 16:12 19阅读 0赞

## 1 题目描述 ##

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

## 2 题目示例 ##

![在这里插入图片描述][2752ee6e5dec45f1bdfbd2d28510d3c0.png]  
![在这里插入图片描述][d4e9e3bf8d51454f93cac2a94fddbc88.png]  
示例 3：

输入：root = \[\]  
输出：\[\]

## 3 题目提示 ##

树中节点数目范围在 \[0, 100\] 内  
\-100 <= Node.val <= 100

## 4 思路 ##

**递归：**  
这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点root的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root为根节点的整棵子树的翻转。  
**复杂度分析**  
时间复杂度:o(N)，其中N为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。  
·空间复杂度:O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即O(log N)。而在最坏情况下，树形成链状，空间复杂度为O(N)。

**迭代：**

递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。  
广度优先遍历需要额外的数据结构–队列，来存放临时遍历到的元素。  
深度优先遍历的特点是一竿子插到底，不行了再退回来继续;而广度优先遍历的特点是层层扫荡。  
所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。  
对当前元素调换其左右子树的位置，然后:  
判断其左子树是否为空，不为空就放入队列中判断其右子树是否为空，不为空就放入队列中  
时间复杂度:同样每个节点都需要入队列/出队列—次，所以是o(n)  
空间复杂度:最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是n/2个，所以时间复杂度是0(n)

## 5 我的答案 ##

**递归：**

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
    }

**迭代：**

class Solution {
        
    	public TreeNode invertTree(TreeNode root) {
        
    		if(root==null) {
        
    			return null;
    		}
    		//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
    		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.add(root);
    		while(!queue.isEmpty()) {
        
    			//每次都从队列中拿一个节点，并交换这个节点的左右子树
    			TreeNode tmp = queue.poll();
    			TreeNode left = tmp.left;
    			tmp.left = tmp.right;
    			tmp.right = left;
    			//如果当前节点的左子树不为空，则放入队列等待后续处理
    			if(tmp.left!=null) {
        
    				queue.add(tmp.left);
    			}
    			//如果当前节点的右子树不为空，则放入队列等待后续处理
    			if(tmp.right!=null) {
        
    				queue.add(tmp.right);
    			}
    			
    		}
    		//返回处理完的根节点
    		return root;
    	}
    }

[2752ee6e5dec45f1bdfbd2d28510d3c0.png]: https://img-blog.csdnimg.cn/2752ee6e5dec45f1bdfbd2d28510d3c0.png
[d4e9e3bf8d51454f93cac2a94fddbc88.png]: https://img-blog.csdnimg.cn/d4e9e3bf8d51454f93cac2a94fddbc88.png