题目：

翻转一棵二叉树

样例

1         1 / \       / \2   3  => 3   2   /       \  4         4

挑战

递归固然可行，能否写个非递归的？

解题:

递归比较简单，非递归待补充

Java程序：

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {    /**     * @param root: a TreeNode, the root of the binary tree     * @return: nothing     */    public void invertBinaryTree(TreeNode root) {        // write your code here        invertTree(root);            }    public TreeNode invertTree(TreeNode root){        if( root ==null){            return root;        }        TreeNode rleft= root.left;        root.left = invertTree(root.right);        root.right = invertTree(rleft);        return root;    }}

总耗时: 994 ms

Python程序：

"""Definition of TreeNode:class TreeNode:    def __init__(self, val):        self.val = val        self.left, self.right = None, None"""class Solution:    # @param root: a TreeNode, the root of the binary tree    # @return: nothing    def invertBinaryTree(self, root):        # write your code here        self.invertTree(root)            def invertTree(self,root):        if root == None:            return root        rlft = root.left        root.left = self.invertTree(root.right)        root.right = self.invertTree(rlft)        return root

总耗时: 118 ms

参考剑指OfferP127改进了下程序，更容易理解了

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {    /**     * @param root: a TreeNode, the root of the binary tree     * @return: nothing     */    public void invertBinaryTree(TreeNode root) {        // write your code here        invertTree(root);    }    public void invertTree(TreeNode root){        if( root ==null){            return;        }        if(root.left == null && root.right ==null){            return;        }        TreeNode tmp= root.left;        root.left = root.right;        root.right = tmp;        if(root.left!=null){            invertTree(root.left);        }        if(root.right!=null){            invertTree(root.right);        }    }}

 

"""Definition of TreeNode:class TreeNode:    def __init__(self, val):        self.val = val        self.left, self.right = None, None"""class Solution:    # @param root: a TreeNode, the root of the binary tree    # @return: nothing    def invertBinaryTree(self, root):        # write your code here        if root == None:            return        if root.left==None and root.right ==None:            return        tmp = root.left        root.left = root.right        root.right = tmp        if root.left!=None:            self.invertBinaryTree(root.left)        if root.right!=None:            self.invertBinaryTree(root.right)