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

Swift 翻转二叉树 invert binary tree in Swift

Swift 翻转二叉树 invert binary tree in Swift - 敏捷大拇指 - Swift 翻转二叉树 invert binary tree in Swift





1、定义树:

[Swift] 纯文本查看 复制代码
class Tree {  
  var key: Int
  var leftTree: Tree?
  var rightTree: Tree?

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





2、非递归实现

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

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


[Swift] 纯文本查看 复制代码
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)
      }
    }
  }
}





3、递归实现

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

[Swift] 纯文本查看 复制代码
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)
  }
}





作者:KittenYang