Swift 翻转二叉树

已经被玩烂的题目，纯粹好玩，直接上代码吧。

• 定义树：

class Tree {  
  var key: Int
  var leftTree: Tree?
  var rightTree: Tree?

  init(key: Int) {
    self.key = key
  }
}

• 非递归实现

思路：广度优先。从上往下，从左往右。到达一层，从左到右翻完这一层的节点，再翻下一层。通过数组的方式实现节点的保存。O(n)。

这里一开始我踩了个坑，忘记每次把根节点移除了，切记。

func invertNonRecursive(root: Tree) {  
  var nodes = [Tree]()
  nodes.append(root)
  while !nodes.isEmpty {
    if let node = nodes.first {
      nodes.removeFirst()
      let tempLeftTree = node.leftTree
      node.leftTree = node.rightTree
      node.rightTree = tempLeftTree

      if let leftT = node.leftTree {
        nodes.append(leftT)
      }
      if let rightT = node.rightTree {
        nodes.append(rightT)
      }
    }
  }
}

• 递归实现

思路：深度优先。先翻一次，之后对左右子树递归翻转。O(n)。

func invertBinaryTreeWithRecursive(root: Tree) {  
  let tempTree = root.leftTree
  root.leftTree = root.rightTree
  root.rightTree = tempTree
  if let leftTree = root.leftTree {
    invertBinaryTreeWithRecursive(leftTree)
  }
  if let rightTree = root.rightTree {
    invertBinaryTreeWithRecursive(rightTree)
  }
}