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)
  }
}
上一篇

一些提高开发效率的 Category


下一篇

在 OC 中实现消息的一箭双雕