牛客题霸NC72二叉树的镜像Java题解

二叉树的镜像

http://www.nowcoder.com/questionTerminal/564f4c26aa584921bc75623e48ca3011

牛客题霸NC72二叉树的镜像Java题解
https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=117&&tqId=34994&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
方法1:利用栈
解题思路:利用栈遍历二叉树的所有节点,交换每个节点的左右子节点。

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 {
    public void Mirror(TreeNode root) {
          if(root == null){   //如果roto为null,返回
              return;
          }

          LinkedList<TreeNode> stack = new LinkedList<>();  
          stack.addLast(root);

          while(!stack.isEmpty()){    //利用栈遍历二叉树的所有节点,交换每个节点的左右子节点。

               TreeNode node = stack.removeLast();   

               if(node.left!=null){         //如果左子节点不为null,将左子节点加入到stack中
                   stack.addLast(node.left);
               }
               if(node.right!=null){       //如果右子节点不为null,将右子节点加入到stack中
                   stack.addLast(node.right);
               }

               TreeNode tmp = node.left;    //交换左、右子节点
               node.left = node.right;
               node.right = tmp;
          }
    }
}

方法2:递归
解题思路:递归遍历左右子树,交换每个节点的左右子节点。

/**
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;
        }
        Mirror(root.left);   //递归遍历左子树
        Mirror(root.right);  //递归遍历右子树

        TreeNode node = root.left;  //交换左、右子节点
        root.left = root.right;
        root.right = node;
    }
}
全部评论

相关推荐

07-17 11:56
门头沟学院 Java
感谢东子的收留
熬夜脱发码农:无敌了,这是我看到第二个京东的提前批大佬了我还在畏畏缩缩准备八股算法
点赞 评论 收藏
分享
程序员小白条:这比例牛逼,750:1
点赞 评论 收藏
分享
凉风落木楚山秋:哈工爷200也去吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务