题目:翻转二叉树
注意与对称二叉树区分
题解:
解法一:递归
这道题比较简单,所以有许多思路,我先展示个人认为最容易理解的递归
1.先处理业务,再完成向下递归的操作
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode tmp = root.left; // 交换左右儿子
root.left = root.right;
root.right = tmp;
invertTree(root.left); // 翻转左子树
invertTree(root.right); // 翻转右子树
return root;
}
}
2.使用临时变量存储递归后的节点的左右
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;
}
}
解法二:栈
这里借用Krahets的代码进行讲解
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null) stack.add(node.left);
if (node.right != null) stack.add(node.right);
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
}
图解:
root出栈 root.left,root.right入栈
进行出栈-交换-入栈
以此类推
一次出栈两个并交换再入栈,直到为空...
那么以上就是全部题解了,欢迎大家补充更多解题思路,如有问题也欢迎大家指正!