精华内容
参与话题
问答
  • 二叉树镜像(破坏二叉树和不破坏二叉树使用非递归实现求解二叉树镜像) 实现过程如下所示: package cn.edu.nwu.tree; import java.util.Stack; /** * @author jcm * *时间 2016年9月16日 */ public class...

    求二叉树镜像(破坏二叉树和不破坏二叉树使用非递归实现求解二叉树镜像)

    实现过程如下所示:

    package cn.edu.nwu.tree;
    
    import java.util.Stack;
    
    /**
     * @author jcm
     *
     *时间 2016年9月16日
     */
    public class GetTreeNodeMirror {
    	public static void main(String[] args) {
    		TreeNode root = CreateBinaryTree.createTreeNode();
    		System.out.println("交换前的二叉树");
    		GetTreeNodeInOrderTraver.inOrderRecursion(root);
    		System.out.println();
    		System.out.println("递归实现二叉树中序遍历");
    		GetTreeNodeInOrderTraver.inOrder(getTreeNodeCopyMirror(root));
    		System.out.println();
    		System.out.println("非递归实现二叉树中序遍历");
    		getTreeNodeMirror(root);
    		GetTreeNodeInOrderTraver.inOrderRecursion(root);
    	}
    	/**
    	 * 求二叉树的镜像
    	 * 这个方法可以看出,他已经破坏了原来的二叉树
    	 * (1)如果二叉树为空,直接return
    	 * (2)如果二叉树不为空,求左子树和右子树的镜像
    	 * (3)交换左子树和右子树 
    	 * (4)原来的树根直接指向交换后的左子树和右子树
    	 * @param root
    	 * @return
    	 */
    	private static void getTreeNodeMirror(TreeNode root){
    		if(root == null){  
                return;  
            }  
            Stack<TreeNode> stack = new Stack<TreeNode>();  
            stack.push(root);  
            while( !stack.isEmpty() ){  
                TreeNode current = stack.pop();  
                // 交换左右孩子  
                TreeNode temp = current.rightRight;  
                current.rightRight = current.leftChild;  
                current.leftChild = temp;  
                if(current.rightRight != null){  
                    stack.push(current.rightRight);  
                }  
                if(current.leftChild != null){  
                    stack.push(current.leftChild);  
                }  
            }
    	}
    	/**
    	 * 求二叉树的镜像
    	 * 这个方法可以看出,如果不能破坏二叉树,则需要定义一个新节点,分别指向二叉树的左子树和右子树
    	 * (1)如果二叉树为空,返回空 
    	 * (2)如果二叉树不为空,求左子树和右子树的镜像,
    	 * (3)交换左子树和右子树 
    	 * @param root
    	 * @return
    	 */
    	private static TreeNode getTreeNodeCopyMirror(TreeNode root){
    		if(root == null){  
                return null;  
            }  
            Stack<TreeNode> stack = new Stack<TreeNode>();  
            Stack<TreeNode> newStack = new Stack<TreeNode>();  
            stack.push(root);  
            TreeNode newRoot = new TreeNode(root.data);  
            newStack.push(newRoot);  
            while(!stack.isEmpty()){  
                TreeNode current = stack.pop();  
                TreeNode newCur = newStack.pop();  
                if(current.rightRight != null){  
                    stack.push(current.rightRight);  
                    newCur.leftChild = new TreeNode(current.rightRight.data);  
                    newStack.push(newCur.leftChild);  
                }  
                if(current.leftChild != null){  
                    stack.push(current.leftChild);  
                    newCur.rightRight = new TreeNode(current.leftChild.data);  
                    newStack.push(newCur.rightRight);  
                }  
            }  
            return newRoot;  
    	}
    }
    


    展开全文
  • 二叉树镜像

    2018-04-09 20:23:10
    操作给定的二叉树,将其变换为源二叉树镜像 分析: 左节点和右节点交换;然后实现左右子树的递归。 代码: /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; ...
    • 题目描述:
      操作给定的二叉树,将其变换为源二叉树的镜像
    • 分析:
      左节点和右节点交换;然后实现左右子树的递归。
    • 代码:
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public void Mirror(TreeNode root) {
            if(root == null)
                return;
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            Mirror(root.left);
            Mirror(root.right);
        }
    }
    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 5,831
精华内容 2,332
关键字:

二叉树镜像