首页 > 试题广场 > 二叉树的镜像
[编程题]二叉树的镜像
操作给定的二叉树,将其变换为源二叉树的镜像。

输入描述:
二叉树的镜像定义:源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

推荐
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==NULL){
            return;
        }
        TreeNode *tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

编辑于 2015-06-19 17:41:47 回复(50)
/* 先前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换它的两个子节点,
当交换完所有的非叶子结点的左右子结点之后,就得到了树的镜像 */
/**
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;
        if(root.left == null && root.right == null)
            return;
        
        TreeNode pTemp = root.left;
        root.left = root.right;
        root.right = pTemp;
        
        if(root.left != null)
            Mirror(root.left);
        if(root.right != null)
            Mirror(root.right);
    }
}

发表于 2016-08-29 08:29:15 回复(21)
class Solution {
public:
	void Mirror(TreeNode *pRoot) {
        //递归实现
        /*if(pRoot==NULL)
            return;
        TreeNode *ptemp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=ptemp;
        if(pRoot->left)
            Mirror(pRoot->left);
        if(pRoot->right)
            Mirror(pRoot->right);*/
        //非递归实现
        if(pRoot==NULL)
            return;
        stack<TreeNode*> stackNode;
        stackNode.push(pRoot);
        while(stackNode.size()){
            TreeNode* tree=stackNode.top();
            stackNode.pop();
            if(tree->left!=NULL || tree->right!=NULL){
                TreeNode *ptemp=tree->left;
                tree->left=tree->right;
                tree->right=ptemp;
            }
            if(tree->left)
                stackNode.push(tree->left);
            if(tree->right)
                stackNode.push(tree->right);
        }
	}
};

编辑于 2015-07-07 15:50:30 回复(29)
class Solution {
public:
    void Mirror(TreeNode *p) {
	if(p){
            swap(p -> left, p -> right);
            Mirror(p -> left);
            Mirror(p -> right);
        }
    }
};

发表于 2015-08-22 23:40:48 回复(10)

python解法:


class Solution:

    def Mirror(self, root):
        # write code here
        if not root:
            return root
        node=root.left
        root.left=root.right
        root.right=node
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root
发表于 2017-10-13 21:36:44 回复(20)
import java.util.Stack;

public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null||node.right != null){
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            if(node.left!=null){
				stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        } 
    }
}

发表于 2016-05-11 22:18:41 回复(14)
class Solution {
public:
         //栈的非递归
	 void Mirror(TreeNode *pRoot) {
		 if (pRoot == NULL)return;
		 stack<TreeNode*> st;
		 TreeNode* p = NULL;
		 st.push(pRoot);
		 while (st.size())
		 {
			 p = st.top();
			 st.pop();
			 swap(p->left, p->right);
			 if (p->left)st.push(p->left);
			 if (p->right)st.push(p->right);
		 }
	 }  //队列的非递归
    void Mirror(TreeNode *pRoot) {
		 if (pRoot == NULL)return;
		 queue<TreeNode*> qu;
		 TreeNode* p = NULL;
		 qu.push(pRoot);
		 while (qu.size())
		 {
			 p = qu.front();
			 qu.pop();
			 swap(p->left, p->right);
			 if (p->left)qu.push(p->left);
			 if (p->right)qu.push(p->right);
		 }
    }
    //递归
    void Mirror(TreeNode *pRoot) {
		 if (pRoot == NULL)return;
		 swap(pRoot->left, pRoot->right);
		 Mirror(pRoot->left);
		 Mirror(pRoot->right);
    }
};

编辑于 2016-08-07 20:54:31 回复(6)

题目描述

image

解题思路

我们或许还记得递归的终极思想是数学归纳法,我们思考递归的时候一定不要去一步一步看它执行了啥,只会更绕。我们牢牢记住,思考的方式是我们首先假设子问题都已经完美处理,我只需要处理一下最终的问题即可,子问题的处理方式与最终那个处理方式一样,但是问题规模一定要以1的进制缩小。最后给一个递归出口条件即可。

对于本题,首先假设root的左右子树已经都处理好了,即左子树自身已经镜像了,右子树自身也镜像了,那么最后一步就是交换左右子树,问题解决。所以我只需要将root.leftroot.right交换即可。下面进入递归,就是处理子问题。子问题的处理方式与root一样,只是要缩小问题规模,所以只需要考虑root.left是什么情况,root.right是什么情况即可。

我的答案

public class Solution {
    public void Mirror(TreeNode root) {
        reverseTree(root);
    }

    private void reverseTree(TreeNode root){
        //为空则结束
        if(root == null){
            return;
        }
        //假设root两边的子树自己都已经翻转成功了,那么只需要再将左右子树互换一下就成功了
        //交换root的左右子树
        swap(root);

        //左右子树翻转自己去处理就行了,我们规定每个子树的root都跟最终的root处理方式一样即可
        reverseTree(root.left);
        reverseTree(root.right);
    }

    private void swap(TreeNode root){
        TreeNode node = null;
        node = root.left;
        root.left = root.right;
        root.right = node;
    }
}
发表于 2019-03-07 17:43:16 回复(6)
事实上二叉树的原理很简单,只是我不熟练
发表于 2017-09-05 20:50:50 回复(0)
//非递归, 层次遍历+swap
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
		if (!pRoot) return;
        vector<TreeNode*> vv;
        vv.push_back(pRoot);
        while (!vv.empty()) {
            vector<TreeNode*> t;
            for (auto &i : vv) {
                swap(i->left, i->right);
                if (i->left) t.push_back(i->left);
                if (i->right) t.push_back(i->right);
            }
            vv.swap(t);
        }
    }
};

编辑于 2015-11-25 22:43:22 回复(2)
   1. 解法
    //自上而下的递归调用
    void Mirror(TreeNode *pRoot) {
    if(pRoot != NULL){
            //先交换当前节点的两个子树节点
            TreeNode *tmpNode = pRoot->left;
            pRoot->left = pRoot->right;
            pRoot->right = tmpNode;
            //对交换后的节点做同样的事。
            Mirror(pRoot->left);
            Mirror(pRoot->right);
        }
    }

    2.我觉得这题和《剑指offer》中的42题(字符串操作)思路有点像:
    42题要求翻转单词顺序:"I am a student."  ->  "student. a am I"
    第一步:翻转所有的字符,eg: "I am a student."  ->  ".tneduts a ma I"
    第二步:再翻转每个单词中的顺序,eg:  ".tneduts a ma I"  ->   "student. a am I"

    3.其他相近的树操作的题目:
    对称树:https://leetcode.com/problems/symmetric-tree/#/description
    相等树:https://leetcode.com/problems/same-tree/#/description
    
发表于 2017-04-05 15:45:27 回复(2)
class Solution {
public:
    void Mirror(TreeNode *p)
    {
		if(p==NULL) return;
        TreeNode *tmp=p->left;
        p->left=p->right;
        p->right=tmp;
        Mirror(p->left);
        Mirror(p->right);
    }
};

发表于 2016-08-15 01:09:14 回复(1)
Python解法:
class Solution:
    def Mirror(self, root):
        # write code here
        if root:#如果存在根节点
            root.left,root.right=root.right,root.left#根节点左右交换,俩变量交换也可以这样写
            self.Mirror(root.left)#递归调用左节点
            self.Mirror(root.right)#递归调用右节点
            return root#返回节点
        else:
            return #else无节点时直接return

编辑于 2018-11-07 21:59:29 回复(0)

递归解法(JavaScript)

function Mirror(root)
{
    if(root === null) return root;
    [root.left, root.right] = [root.right, root.left];
    Mirror(root.left);
    Mirror(root.right);
}

非递归解法

function Mirror(root)
{
    if(root === null) return root;
    let stack = [root];
    while(stack.length){
        let x = stack.pop();
        [x.left, x.right] = [x.right, x.left];
        if(x.left) stack.push(x.left);
        if(x.right) stack.push(x.right);
    }
}
编辑于 2018-04-25 10:46:38 回复(1)
最佳答案,没有之一:
public class Solution {
    public void Mirror(TreeNode root) {
        if(root != null){
            Mirror(root.left);
            Mirror(root.right);
            TreeNode temp = root.left;
            root.left=root.right;
            root.right = temp;
        } 
    }
}
发表于 2015-08-30 23:12:23 回复(13)
   //凡是二叉树相关的问题一定要好好理解二叉树的递归定义,
 void Mirror(TreeNode *pRoot) {
        if (pRoot == NULL)
            return;
        //交换左右孩子的次序可以在递归之前,也可以在递归之后,但是感觉在递归之后比较好
        TreeNode *ptemp;
        ptemp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = ptemp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return ;
    }
发表于 2015-09-29 13:38:07 回复(2)
  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);
    }


发表于 2018-08-11 12:29:46 回复(0)
class Solution {
public:
    void Mirror(TreeNode *p) {
         if(!p) return ;
         Mirror(p->left);
         Mirror(p->right);
         swap(p->left,p->right);
    }
};

发表于 2017-05-31 20:57:29 回复(0)
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (pRoot==NULL || (pRoot->left==NULL && pRoot->right==NULL)) {
            return;
        }
        TreeNode *treeTemp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = treeTemp;
        if(pRoot->left)
        	Mirror(pRoot->left);
        if(pRoot->right)
        	Mirror(pRoot->right);
    }
};

发表于 2015-10-23 11:26:44 回复(0)
/**
层序遍历,把每个节点的左右节点交换
*/
import java.util.*;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        TreeNode temp;
        while(!queue.isEmpty()){
            root = queue.poll();
            temp = root.left;
            root.left = root.right;
            root.right = temp;
            if(root.left != null){
                queue.add(root.left);
            }
            if(root.right != null){
                queue.add(root.right);
            }

        }


    }
}
发表于 今天 06:53:35 回复(0)
///JAVA比较经典的方法
///1、第一种方法是用栈递归
import java.util.Stack;
public class Solution {
    public void Mirror(TreeNode root) {
        
        if(root==null)
            return;
        
        if(root.left==null&&root.right==null)
            return;
        
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            if(node.left!=null||node.right!=null){
                TreeNode ptemp=node.right;
                node.right=node.left;
                node.left=ptemp;
            }
           
            
            if(node.left!=null){
                stack.push(node.left);
            }
            
            if(node.right!=null){
                stack.push(node.right);
            }
        }
    }
}

///2、第二种方法是用先序+交换


public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            return;
         
        TreeNode pTemp = root.left;
        root.left = root.right;
        root.right = pTemp;
         
        if(root.left != null)
            Mirror(root.left);
        if(root.right != null)
            Mirror(root.right);
    }
}

编辑于 2019-08-18 16:29:51 回复(0)