欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的镜像

程序员文章站 2022-06-01 08:42:25
...

二叉树的镜像


 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {

        //方法二:精简递归方法
      public void Mirror2(TreeNode root) {
        TreeNode tmp = null;
        if (root != null)
            {
            tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            if (root.left != null)
                Mirror2(root.left);
            if (root.right != null)
                Mirror2(root.right);
        }
    }

       //方法一:一般递归方法
    public void Mirror(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null))
        {
            return;
        }
       Switch(root);

    }
    public void Switch(TreeNode root){

        if(root.left!=null&&root.right!=null){

          TreeNode temp=root.left;
          root.left=root.right;
          root.right=temp;
        }else if(root.left==null)
        {
            root.left=root.right;
            root.right=null;

        }else if(root.right==null)
        {
            root.right=root.left;
            root.left=null;
        }else{
            return;
        }
        if(root.left!=null)
        {
             Switch(root.left);
        }

        if(root.right!=null)
        {
            Switch(root.right);
        }

    }
    //二叉树的中序遍历
    public void inOrder(TreeNode head){

         if(head!=null){
             inOrder(head.left);
             visit(head);
             inOrder(head.right);
         }
    }
    public void visit(TreeNode node){

         System.out.print(node.val+" ");
    }
    public static void main(String[]args){
       // System.out.println("Hello");
        Solution s=new Solution();
        TreeNode head=new TreeNode(8);
        head.left=new TreeNode(6);
        head.right=new TreeNode(10);
        head.left.left=new TreeNode(5);
        head.left.right=new TreeNode(7);
        head.right.left=new TreeNode(9);
        head.right.right=new TreeNode(11);

        TreeNode head2=new TreeNode(8);
        head2.left=new TreeNode(7);
        head2.left.left=new TreeNode(6);
        head2.left.left.left=new TreeNode(5);
        head2.left.left.left.left=new TreeNode(4);

        s.inOrder(head2);
        System.out.println();
        s.Mirror(head2);
        s.inOrder(head2);

    }
}

二叉树的镜像