Invert a binary tree.
4 / 2 7 / / 1 3 6 9
to
4 / 7 2 / / 9 6 3 1
解法1:
本质是输的先序遍历
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ # invert self.left # invert self.right if not root: return None root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root
解法2,上述DFS的迭代解法:
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return None stack = [root] while stack: node = stack.pop() node.left, node.right = node.right, node.left if node.right: stack.append(node.right) if node.left: stack.append(node.left) return root
解法3,使用BFS:
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return None nodes = [root] while nodes: nodes2 = [] for node in nodes: node.left, node.right = node.right, node.left if node.left: nodes2.append(node.left) if node.right: nodes2.append(node.right) nodes = nodes2 return root