【leetcode】solution in java——Easy4

转载请注明原文地址：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