题解 | #二叉树的镜像#

二叉树的镜像

http://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7

1. python3 解法： dfs遍历的同时交换，使用了一个栈没有递归

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot ):
        # write code here
        if pRoot == None:
            return None
        node_list = []
        node_list.append(pRoot)
        while node_list:
            node = node_list.pop()
            left = node.left
            node.left = node.right
            node.right = left
            if node.left:
                node_list.append(node.left)
            if node.right:
                node_list.append(node.right)
        return pRoot

2. java解法：递归

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot==null){
            return pRoot;
        }
        TreeNode left = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = left;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

3. go解法递归。用递归是因为go的栈得自己造。。

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
*/
func Mirror( pRoot *TreeNode ) *TreeNode {
    // write code here
    if pRoot == nil{
        return pRoot
    }
    left := pRoot.Left
    pRoot.Left  = pRoot.Right
    pRoot.Right = left
    Mirror(pRoot.Left)
    Mirror(pRoot.Right)
    return pRoot
}