[名企面试知识点][Java]二叉树的镜像
发布于 2017-03-14 13:53 1261 次浏览 0 赞 来自 笔试面试  

题目描述

操作给定的二叉树,将其变换为源二叉树的镜像。

输入描述

二叉树的镜像定义:

源二叉树  

        8
      /  \
     6   10
    / \  / \
   5  7 9  11 

镜像二叉树 

        8
      /  \
     10   6
    / \  / \
   11 9 7  5

输出描述

源二叉树的镜像

题目分析

节点描述:

  

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

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

解法  运行时间:38ms  占用内存:688k 

public class Solution {
   public void Mirror(TreeNode root) {        
       if(root==null) return;

       //交换左右子节点
       TreeNode tempNode;
       tempNode = root.left;
       root.left = root.right;
       root.right = tempNode;

       Mirror(root.left);
       Mirror(root.right);
   }
}

思路:从根节点开始依次递归遍历整棵树,如果节点不为空,就交换它的左右子节点(对象的赋值,相应的左右指针也会改变)。

添加回复
回到顶部