题目:
方法一: 后序遍历
后序遍历,交换当前root的左右节点即可!
注意: 不可以使用DFS中序遍历 ! 因为子节点会重复(因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子了!))
递归三步曲:
-
确定递归函数的参数和返回值
参数就是要传入节点的指针,不需要其他参数了,通常此时定下来主要参数,如果在写递归的逻辑中发现还需要其他参数的时候,随时补充。
返回值的话其实也不需要 !!!,但是题目中给出的要返回root节点的指针,可以直接使用题目定义好的函数,所以返回root即可 -
确定终止条件
当前节点为空的时候,就返回null -
确定单层递归的逻辑
因为是后序遍历,所以先反转左子树,反转右子树,最后进行交换左右孩子节点。 换成前序遍历也可以,中序遍历不行 !
class Solution {
public TreeNode mirrorTree(TreeNode root) {
check(root);
return root;
}
void check(TreeNode root){
if(root==null){
return;
}
// 后序
check(root.left);
check(root.right);
// 交换
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
方法一: 辅助栈 ※
栈是后进先出,头插头取!
二叉树中能够用递归的,我们大多也可以用栈来实现。栈的访问是一种自顶向下的访问,因此我们需要在左右子节点入栈后直接交换,然后再访问后续栈中内容。
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;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/89330.html