这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 综合技术 » 基础知识 » Java开发编程求二叉树的镜像两种方法介绍及源码解决思路

共3条 1/1 1 跳转至

Java开发编程求二叉树的镜像两种方法介绍及源码解决思路

菜鸟
2020-12-11 17:51:01     打赏

今天本文章主要介绍了Java编程求二叉树的镜像两种方法介绍,分享了两种方法,递归与非递归,每种方法又分别介绍了两种解决思路,具有一定参考价值,需要的朋友可以了解下。


给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像。

仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤。这两棵树的根节点相同,但他们的左右两个子节点交换了位置。因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树

解法1(递归)

思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理。


  /*classTreeNode{
  intval;
  TreeNodeleft=null;
  TreeNoderight=null;
  publicTreeNode(intval){
  this.val=val;
  }
  }*/
  publicstaticvoidmirrorTree(TreeNoderoot)
  {
  if(root==null)
  return;
  //交换该节点指向的左右节点。
  TreeNodetemp=root.left;
  root.left=root.right;
  root.right=temp;
  //对其左右孩子进行镜像处理。
  mirrorTree(root.left);
  mirrorTree(root.right);
  }


交换过程如下图:

交换根节点的两个子节点之后,我们注意到值为10,6的结点的子节点仍然保持不变,因此我们还需要交换这两个结点的左右子节点。交换之后的结果分别为第三课树和第四颗树。做完这两次交换之后,我们已经遍历完所有的非叶子结点。此时交换之后的树刚好就是原始树的镜像。

思路2:如果当前节点为null,返回null,否则先分别对该节点的左右孩子进行镜像处理,然后将该节点的左指针指向右孩子,右指针指向左孩子,对该节点进行镜像处理。

  /*classTreeNode{
  intval;
  TreeNodeleft=null;
  TreeNoderight=null;
  publicTreeNode(intval){
  this.val=val;
  }
  }*/
  publicstaticTreeNodemirrorTree1(TreeNoderoot)
  {
  if(root==null)
  returnnull;
  //对左右孩子镜像处理
  TreeNodeleft=mirrorTree1(root.left);
  TreeNoderight=mirrorTree1(root.right);
  //对当前节点进行镜像处理。
  root.left=right;
  root.right=left;
  returnroot;
  }


解法2(非递归)

思路1:层次遍历,根节点不为null将根节点入队,判断队不为空时,节点出队,交换该节点的左右孩子,如果左右孩子不为空,将左右孩子入队。



  publicstaticvoidmirrorTreeWithQueue(TreeNoderoot)
  {
  if(root==null)
  return;
  //如果树为null直接返回。否则将根节点入队列。
  Queue<TreeNode>queue=newLinkedList<TreeNode>();
  queue.add(root);
  while(!queue.isEmpty())
  {
  //队列不为空时,节点出队,交换该节点的左右子树。
  TreeNoderoot1=queue.poll();
  /*TreeNodeleft,right;
  left=root1.left;
  right=root1.right;
  root1.right=left;
  root1.left=right;
  */
  Swap(root);
  if(root1.right!=null)
  {
  queue.add(root1.right);
  //如果左子树不为null入队
  }
  if(root1.left!=null)
  {
  queue.add(root1.left);
  //如果右子树不为null入队。
  }
  }
  }
  publicstaticvoidSwap(TreeNoderoot)
  {
  TreeNodetemp;
  temp=root.right;
  root.right=root.left;
  root.left=temp;
  }



思路2:先序遍历,如果根节点不为null将根节点入栈,当栈不为null出栈,交换左右节点,如果左右节点不为null入栈。

  publicstaticvoidmirrorTreeWithStack(TreeNoderoot)
  {
  if(root==null)
  return;
  Stack<TreeNode>stack=newStack<TreeNode>();
  stack.push(root);
  while(!stack.isEmpty())
  {
  //当栈不为null时出栈,交换左右子树。
  TreeNoderoot1=stack.pop();
  /*TreeNodeleft,right;
  left=root1.left;
  right=root1.right;
  root1.right=left;
  root1.left=right;*/
  Swap(root);
  if(root1.right!=null)
  {
  //右子树不为null入栈
  stack.push(root1.right);
  }
  if(root1.left!=null)
  {
  //左子树不为null入栈
  stack.push(root1.left);
  }
  }
  }
  publicstaticvoidSwap(TreeNoderoot)
  {
  TreeNodetemp;
  temp=root.right;
  root.right=root.left;
  root.left=temp;
  }


以上就是本文关于Java编程求二叉树的镜像两种方法介绍的全部内容,希望对大家有所帮助,最后想要了解更多Java信息的同学可以前往扣丁学堂官网咨询,扣丁学堂Java培训深受学员的喜爱。扣丁学堂不仅有专业的老师和与时俱进的课程体系,还有大量的Java视频教程供学员观看学习哦。扣丁学堂java技术交流群:487098661。微 信 号:codingbb



高工
2020-12-15 21:36:15     打赏
2楼

思路分享的不错


工程师
2020-12-15 21:55:17     打赏
3楼

思路还是挺好的


共3条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]