## The inverse of an empty tree is the empty tree.

## The inverse of a tree with root r, and subtrees right and left, is a tree with root r, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

### For example:

` For example Given binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 `

`invert and return 1 / \ 3 2 / \ / \ 7 6 5 4 `

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode right = invertTree(root.right); TreeNode left = invertTree(root.left); root.left = right; root.right = left; return root; }

### Complexity Analysis

Because of recursion, O(h)O(h) function calls will be placed on the stack in the worst case, where hh is the height of the tree. Because h\in O(n)h∈O(n), the space complexity is O(n).

--

Posted By Blogger to HDGEM at 3/04/2017 07:36:00 AM