Invert a binary tree.
Example:
Input: 4 / 2 7 / / 1 3 6 9 Output: 4 / 7 2 / / 9 6 3 1
分析¶
最开始想到的方法是递归,而且也很简单。
public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmp = root.right; root.right = root.left; root.left = tmp; invertTree(root.left); invertTree(root.right); return root; }
使用DFS的递归:
class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmpRight = root.right; root.right = invertTree(root.left); root.left = invertTree(tmpRight); return root; } }
递归的时间和空间复杂度是O(n), n是节点数。
还有迭代的方法
public TreeNode invertTreeQueue(TreeNode root) { if (root == null) return null; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { TreeNode current = queue.poll(); TreeNode temp = current.left; current.left = current.right; current.right = temp; if (current.left != null) queue.add(current.left); if (current.right != null) queue.add(current.right); } return root; }
近期评论