求二叉树中两结点的最小公共祖先

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def FindLCA(node1, node2):
  # Special cases.
  if not node1 or not node2:
    return None
  if node1 is node2:
    return node1

  # Get the first branch path.
  ancestors1 = set()
  while node1:
    ancestors1.add(node1)
    node1 = node1.parent

  # Check if any ancestor of node2 is in the first branch path.
  while node2:
    if node2 in ancestors1:
      return node2    # Got it, the LCA.
    node2 = node2.parent

  # These two nodes have no common ancestor.
  return None

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def FindLCA(node1, node2):
  # Special cases.
  if not node1 or not node2:
    return None
  if node1 is node2:
    return node1

  # Gets each node's depth.
  depth = lambda node: depth(node.parent) + 1 if node else 0
  depth1 = depth(node1)
  depth2 = depth(node2)

  # Pulls up the lower node and makes the two nodes in the same depth.
  mindepth = min(depth1, depth2)
  for i in xrange(depth1 - mindepth): node1 = node1.parent
  for i in xrange(depth2 - mindepth): node2 = node2.parent

  # Finds the common ancestor.
  while node1 and node2:
    if node1 is node2: return node1
    node1 = node1.parent
    node2 = node2.parent

  return None

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Dir:
  (Undef, Left, Right) = range(3)

def FindNodes(root, nodeSet, findAll=True):
  if not root or not nodeSet:
    return None

  pathDict = {}
  path = []
  curr = root
  while curr or path:
    while curr:   # Go down along left branch
      path.append((curr, Dir.Left))
      if curr in nodeSet:
        pathDict[curr] = list(path)
        nodeSet.remove(curr)
        if not nodeSet or not findAll:
          return pathDict
      curr = curr.left
    (curr, dir) = path.pop()
    while dir == Dir.Right:   # Back from right branch
      if not path: return pathDict
      (curr, dir) = path.pop()
    path.append((curr, Dir.Right))  # Trun to right from left
    curr = curr.right

  return pathDict

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def FindLCA(root, node1, node2):
  # Special cases.
  if not root or not node1 or not node2:
    return None
  if node1 is node2:
    return node1

  # Try to find the two nodes in the tree, and get their branch paths.
  nodeSet = set([node1, node2])
  pathDict = FindNodes(root, nodeSet)
  if nodeSet:
    return None

  path1 = [i[0] for i in pathDict[node1]]
  path2 = [i[0] for i in pathDict[node2]]

  # Compare the two paths, find out the LCA.
  lca = None
  minLen = min(len(path1), len(path2))
  for i in xrange(minLen):
    if path1[i] is not path2[i]:
      break
    lca = path1[i]

  return lca

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def FindLCA(root, node1, node2):
  nodeset = set([node1, node2])   # Also supports 3 or more nodes.
  s = []          # A stack to help performing N-L-R traversing.
  lca = None      # Records the most possible least common ancestor.
  mindepth = -1   # The depth of lca.
  while root or s:
    if root:
      if root in nodeset:
        nodeset.remove(root)
        if mindepth < 0:
          # Yeah, found the first node. The lca must be itself or already in s.
          lca = root
          mindepth = len(s)
        if not nodeset:
          break
      s.append(root)
      root = root.left
    else:
      root = s.pop()
      if mindepth > len(s):
        lca = root
        mindepth = len(s)
      root = root.right
  return None if nodeset else lca