Reverse Binary Tree
样例
1 1
/ \ / \
2 3 => 3 2
/ \
4 4
挑战
递归固然可行,能否写个非递归的?
Solution
基本翻转即可
Complexity
时间复杂度 O(n),空间复杂度 非递归O(1) 递归O(h)
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root!=null){
helper(root);
}
return root;
}
public void helper(TreeNode p){
TreeNode temp = p.left;
p.left = p.right;
p.right = temp;
if(p.left!=null)
helper(p.left);
if(p.right!=null)
helper(p.right);
}
public TreeNode invertTree_2(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
TreeNode p = queue.poll();
if(p.left!=null)
queue.add(p.left);
if(p.right!=null)
queue.add(p.right);
TreeNode temp = p.left;
p.left = p.right;
p.right = temp;
}
return root;
}
}
递归版本
"""
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):
if root is None:
return None
if root.left:
self.invertBinaryTree(root.left)
if root.right:
self.invertBinaryTree(root.right)
root.left, root.right = root.right, root.left
return root
非递归版本
"""
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):
if root is None:
return None
queue = [root]
while queue:
front = queue.pop(0)
if front.left:
queue.append(front.left)
if front.right:
queue.append(front.right)
front.left, front.right = front.right, front.left
return root