题解 | #二叉树的镜像#
二叉树的镜像
http://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7
题目的主要信息：
- 将二叉树镜像，即将其所有左右子树交换
我们可以考虑自底向上依次交换二叉树的左右节点。
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：递归（推荐使用）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
因为我们需要将二叉树镜像，意味着每个左右子树都会交换位置，如果我们从上到下对遍历到的节点交换位置，但是它们后面的节点无法跟着他们一起被交换，因此我们可以考虑自底向上对每两个相对位置的节点交换位置，这样往上各个子树也会被交换位置。
自底向上的遍历方式，我们可以采用后序递归的方法。
具体做法：
- step 1：先深度最左端的节点，遇到空树返回，处理最左端的两个子节点交换位置。
- step 2：然后进入右子树，继续按照先左后右再回中的方式访问。
- step 3：再返回到父问题，交换父问题两个子节点的值。
Java实现代码：
import java.util.*;
public class Solution {
public TreeNode Mirror (TreeNode pRoot) {
//空树返回
if(pRoot == null)
return null;
//先递归子树
TreeNode left = Mirror(pRoot.left);
TreeNode right = Mirror(pRoot.right);
//交换
pRoot.left = right;
pRoot.right = left;
return pRoot;
}
}
C++实现代码：
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
//空树返回
if(pRoot == NULL)
return NULL;
//先递归子树
TreeNode* left = Mirror(pRoot->left);
TreeNode* right = Mirror(pRoot->right);
//交换
pRoot->left = right;
pRoot->right = left;
return pRoot;
}
};
Python实现代码
class Solution:
def Mirror(self , pRoot: TreeNode) -> TreeNode:
# 空树返回
if not pRoot:
return None
# 先递归子树
left = self.Mirror(pRoot.left)
right = self.Mirror(pRoot.right)
# 交换
pRoot.left = right
pRoot.right = left
return pRoot
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，访问二叉树所有节点各一次
- 空间复杂度：，最坏情况下，二叉树退化为链表，递归栈最大值为
方法二：栈（扩展思路）
知识点：栈
栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
思路：
二叉树中能够用递归的，我们大多也可以用栈来实现。栈的访问是一种自顶向下的访问，因此我们需要在左右子节点入栈后直接交换，然后再访问后续栈中内容。
具体做法：
- step 1：优先检查空树的情况。
- step 2：使用栈辅助遍历二叉树，根节点先进栈。
- step 3：遍历过程中每次弹出栈中一个元素，然后该节点左右节点分别入栈。
- step 4：同时我们交换入栈两个子节点的值，因为子节点已经入栈了再交换，就不怕后续没有交换。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public TreeNode Mirror (TreeNode pRoot) {
//空树
if(pRoot == null)
return null;
//辅助栈
Stack<TreeNode> s = new Stack<TreeNode>();
//根节点先进栈
s.push(pRoot);
while (!s.isEmpty()){
TreeNode node = s.pop();
//左右节点入栈
if(node.left != null)
s.push(node.left);
if(node.right != null)
s.push(node.right);
//交换左右
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
return pRoot;
}
}
C++实现代码：
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
//空树
if(pRoot == NULL)
return NULL;
//辅助栈
stack<TreeNode*> s;
//根节点先进栈
s.push(pRoot);
while (!s.empty()){
TreeNode* node = s.top();
s.pop();
//左右节点入栈
if (node->left != NULL) s.push(node->left);
if (node->right != NULL) s.push(node->right);
//交换左右
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
return pRoot;
}
};
Python实现代码
class Solution:
def Mirror(self , pRoot: TreeNode) -> TreeNode:
# 空树
if not pRoot:
return None
# 辅助栈
s = []
# 根节点先进栈
s.append(pRoot)
while s:
node = s[-1]
s.pop()
if node.left:
# 左右节点入栈
s.append(node.left)
if node.right:
s.append(node.right)
# 交换左右
temp = node.left
node.left = node.right
node.right = temp
return pRoot
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，访问二叉树所有节点各一次
- 空间复杂度：，最坏情况下，二叉树退化为链表，栈的最大空间为
