首页 > 编程语言 > 详细

【leetcode】solution in java——Easy4

时间:2017-02-19 12:11:27      阅读:200      评论:0      收藏:0      [点我收藏+]

转载请注明原文地址:http://www.cnblogs.com/ygj0930/p/6415011.html

16:Invert Binary Tree

此题:以根为对称轴,反转二叉树。

思路:看到二叉树,我们第一时间要想到处理二叉树的常用方法——BFS、DFS,更常用的是DFS。此题我们先用BFS来思考:BFS是逐层每个结点处理,即通过交换每层结点的位置来达到整体交换。我们可以用队列+栈来实现,用队列处理实现按层遍历,用栈实现当前层结点位置倒转,然后从根结点开始,逐层重新建树。无疑,这很麻烦。我们转而思考DFS怎么做:从根结点开始,交换左右子树,然后递归到下一层,交换左右子树......直到倒数第二层,交换左右子树,从而实现整体互换。

牢记DNF三步骤:递归边界返回值、当前层值由递归得出、递归的返回值是什么

public TreeNode invertTree(TreeNode root) {        
        //递归边界的返回值
        if (root==null)    {return null;}
        //当前层处理:值由递归得到
        TreeNode left=root.left;
        TreeNode right=root.right;
        root.left=invertTree(right);
        root.right=invertTree(left);
        //递归的返回值
        return root;    
    }

 

【leetcode】solution in java——Easy4

原文:http://www.cnblogs.com/ygj0930/p/6415011.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!