leetcode 226. Invert Binary Tree (python)

题目

Invert a binary tree.（具体题目参考leetcode官网）

解法1：利用递归(recursive)

递归的将每个节点的左右节点调换

形式1

class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""def invert(node):if not node:return node.left,node.right = node.right,node.leftinvert(node.left)invert(node.right)if not root:return rootinvert(root)return root

形式2（跟简洁，直接用原函数进行递归）

class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""if not root:return Noneroot.left,root.right = self.invertTree(root.right),self.invertTree(root.left)return root

时间复杂度：O(N), N为节点个数
空间复杂度：O(H), H为树的高度

解法2：利用迭代(iterative)

在这边，利用栈或者队列效果是一模一样的，在python中，如果stack = collections.deque(), 那么采用stack.pop()和stack.popleft()都是可以的

class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""if not root:return rootstack = collections.deque()stack.append(root)while stack:node = stack.pop()node.left,node.right = node.right,node.leftif node.left:stack.append(node.left)if node.right:stack.append(node.right)return root

时间复杂度：O(N), N为节点个数
空间复杂度：O(W), W为树的宽度