#initial of BinaryTree
class BinaryTree:
 def __init__(self,rootObj):
  self.val = rootObj
  self.left = None
  self.right = None
 def insertLeft(self,newNode):
  if self.left == None:
self.left = BinaryTree(newNode)
  else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
 def insertRight(self,newNode):
  if self.right == None:
self.right = BinaryTree(newNode)
  else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t

#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
#  18
# 7  11
#3 4 5 6
#1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)

#遞歸版本
def PreOrder(self, node):
 if node:
  print(node.val)
  self.PreOrder(node.left)
  self.PreOrder(node.right)
#循環(huán)版本
def PreOrderLoop(self, node):
 if node == None:
  return
 stack =[]
 print(node.val)
 stack.append(node)
 node = node.left
 while stack!=[] or node:
  while node:
print(node.val)
stack.append(node)
node = node.left
  node = stack[-1].right
  stack.pop()
#ouput: 18 7 3 4 11 5 1 3 6 2 4 

#遞歸版本
def InOrder(self, node):
 if node:
  self.InOrder(node.left)
  print(node.val)
  self.InOrder(node.right)
#循環(huán)版本
def InOrderLoop(self, node):
 if node == None:
  return None
 stack = []
 stack.append(node)
 node = node.left
 while stack!=[] or node:
  while node:
stack.append(node)
node = node.left
  print(stack[-1].val)
  node = stack[-1].right
  stack.pop()
#output：3 7 4 18 1 5 3 11 2 6 4

#遞歸
def PostOrder(self, node):
 if node:
  self.PostOrder(node.left)
  self.PostOrder(node.right)
  print(node.val)
#非遞歸
def PostOrderLoop(self, node):
 if node == None:
  return
 stack =[]
 stack.append(node)
 pre = None
 while stack!=[]:
  node = stack[-1]
  if ((node.left==None and node.right==None) or
 (pre and (pre == node.left or pre ==node.right))):
print(node.val)
pre = node
stack.pop()
  else:
if node.right:
 stack.append(node.right)
if node.left:
 stack.append(node.left)
#output:3 4 7 1 3 5 2 4 6 11 18

def LevelOrder(self, node):
 if node == None:
  return
 stack = []
 stack.append(node)
 while stack!=[]:
  node = stack[0]
  if node.left:
stack.append(node.left)
  if node.right:
stack.append(node.right)
  print(node.val)
  stack.pop(0)
output: 18 7 11 3 4 5 6 1 3 2 4

#遞歸版本
def CountNode(self, root):
 if root == None:
  return 0
 return self.CountNode(root.left) + self.CountNode(root.right) + 1
#非遞歸版本
def CountNodeNotRev(self, root):
 if root == None:
  return 0
 stack = []
 stack.append(root)
 index = 0
 while index<len(stack):
  if stack[index].left:
stack.append(stack[index].left)
  if stack[index].right:
stack.append(stack[index].right)
  index += 1
 print(len(stack))
output: 11

def getTreeDepth(self, root):
 if root == None:
  return 0
 left = self.getTreeDepth(root.left) + 1
 right = self.getTreeDepth(root.right) + 1
 return left if left>right else right

def countLeaves(self, root):
 if root == None:
  return 0
 if root.left==None and root.right==None:
  return 1
 return self.countLeaves(root.left)+self.countLeaves(root.right)

def getKLevel(self, root, K):
 if root == None: return 0
 if K == 1: return 1
 return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1)

def StrucCmp(self, root1, root2):
 if root1 == None and root2 == None: return True
 elif root1 ==None or root2 == None: return False
 return self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right)

def Mirror(self, root):
 if root == None: return
 tmp = root.left
 root.left = root.right
 root.right = tmp
 self.Mirror(root.left)
 self.Mirror(root.right)

def findLCA(self, root, node1, node2):
 if root == None: return
 if root == node1 or root == node2: return root
 left = self.findLCA(root.left, node1, node2)
 right = self.findLCA(root.right, node1, node2)
 if left and right:
  return root
 return left if left else right

def getDist(self, root, node1, node2):
 lca = self.findLCA(root, node1, node2) #找最低公共祖宗節(jié)點(diǎn)
 level1 = self.FindLevel(lca, node1) #祖節(jié)點(diǎn)到兩個(gè)節(jié)點(diǎn)的距離
 level2 = self.FindLevel(lca, node2)
 return level1+level2
def FindLevel(self, node, target):
 if node == None: return -1
 if node == target: return 0
 level = self.FindLevel(node.left, target)
 if level == -1: level = self.FindLevel(node.right, target)
 if level != -1: return level + 1
 return -1

def findAllAncestor(self, root, target):
 if root == None: return False
 if root == target: return True
 if self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target):
  print(root.val)
  return True
 return False