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