• 周日. 5月 26th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

剑指offer解题报告(Java版)——二叉树的镜像 19

admin

11月 28, 2021

引言

   

发现二叉树的问题很多都是用递归解决的,除了按照剑指offer书中给的递归方法,自己也用栈的方法去实现了,两种方法其实深层次的思想差不多

   

分析问题

   

只要我们前序遍历,或者层次遍历二叉树,如果遇到节点就将左右子树交换,即可,递归基就是节点没有左右子树

   

   

解决问题

   

利用递归方法

   

这里要注意Corner Case的考虑

   

public BinaryTreeNode mirrorRecursively(BinaryTreeNode root) {

if (root == null || (root.leftNode == null && root.rightNode == null))

return root;

// 交换左右子树

BinaryTreeNode tempBinaryTreeNode = root.leftNode;

root.leftNode = root.rightNode;

root.rightNode = tempBinaryTreeNode;

// 递归下去

if (root.leftNode != null) {

mirrorRecursively(root.leftNode);

}

if (root.rightNode != null) {

mirrorRecursively(root.rightNode);

}

return root;

}

   

栈的方法

   

栈的方法其实是模拟递归的方法,首先交换左右孩子,将根节点压入栈中,开始考虑左孩子,这时候左孩子就相当于左子树的根节点

   

如果左孩子不为空,那么同样交换左右孩子,将根节点压入栈中

   

当左孩子无法再下一层时,也就是左孩子没有左右孩子了,那么弹出栈顶元素,将考虑栈顶元素的右孩子,跟递归的思想一模一样

   

public BinaryTreeNode mirrorStack(BinaryTreeNode root)

{

if(root==null)

return null;

BinaryTreeNode node=root;

Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();

while(node!=null || !stack.isEmpty())

{

while(node!=null)

{

BinaryTreeNode temp=node.leftNode;                                

node.leftNode=node.rightNode;

node.rightNode=temp;

   

stack.push(node);

node=node.leftNode;

}

node=stack.pop();

node=node.rightNode;

}

return root;

}

   

测试代码

   

BinaryTreeNode root1=new BinaryTreeNode();

BinaryTreeNode node1=new BinaryTreeNode();

BinaryTreeNode node2=new BinaryTreeNode();

BinaryTreeNode node3=new BinaryTreeNode();

BinaryTreeNode node4=new BinaryTreeNode();

BinaryTreeNode node5=new BinaryTreeNode();

BinaryTreeNode node6=new BinaryTreeNode();

root1.leftNode=node1;

root1.rightNode=node2;

node1.leftNode=node3;

node1.rightNode=node4;

node2.leftNode=node5;

node2.rightNode=node6;

root1.data=8;

node1.data=6;

node2.data=10;

node3.data=5;

node4.data=7;

node5.data=9;

node6.data=11;

BinaryTreeNode root2=new BinaryTreeNode();

BinaryTreeNode a=new BinaryTreeNode();

BinaryTreeNode b=new BinaryTreeNode();

root2.leftNode=a;

root2.rightNode=b;

root2.data=8;

a.data=7;

b.data=2;

MirrorRecursively test=new MirrorRecursively();

BinaryTreeNode rootBinaryTreeNode=test.mirrorRecursively(root1);

System.out.println(root1.rightNode.leftNode.data);

   

《剑指offer解题报告(Java版)——二叉树的镜像 19》有4个想法
  1. Gut Vita™ is a daily supplement that helps consumers to improve the balance in their gut microbiome, which supports the health of their immune system. It supports healthy digestion, even for consumers who have maintained an unhealthy diet for a long time. https://gutvitabuynow.us/

  2. Wow, fantastic weblog format! How long have you ever been running a blog for?
    you made blogging glance easy. The total look of your website is wonderful, let alone
    the content material! You can see similar here dobry sklep

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注