对于一个二叉树，每个结点有三个指针，除了左右子节点指针外还有一个指向右边的结点的指针。现在给定一个二叉树，每个结点的右指针为空，让你把每一层的结点都连起来（默认是完全二叉树）
class TreeNode(object):
def __init__(self,val,left = None,right = None):
self.val = val
self.left = left
self.right = right
self.next = None
class BinaryTree(object):
def __init__(self,root=None):
self.root = root
def preOrder(self):
if not self.root:
return
stack = [self.root]
while stack:
node = stack.pop()
print(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
def inOrder(self):
if not self.root:
return
stack,node = [self.root],self.root.left
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.val)
node = node.right
def postOrder(self):
if not self.root:
return
stack,node,marknode = [self.root],self.root.left,None
while marknode!=self.root:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if not node.right or marknode==node.right:
print(node.val)
node,marknode = None,node
else:
stack.append(node)
node = node.right
def hierar_travel(self):
if not self.root:
return
cur_nodes = [self.root]
while cur_nodes:
print([[node.val,node.next.val if node.next else None] for node in cur_nodes])
nex_nodes = []
for node in cur_nodes:
if node.left:
nex_nodes.append(node.left)
if node.right:
nex_nodes.append(node.right)
cur_nodes = list(nex_nodes)
def build_next_pointer(self): #将每个节点连接到它的右边sibling（默认完全二叉树）
if not self.root:
return
cur_nodes = [self.root]
while cur_nodes and cur_nodes[0].left:
nex_nodes = []
for cur in cur_nodes:
if cur.left:
nex_nodes.append(cur.left)
if cur.right:
nex_nodes.append(cur.right)
cur.left.next = cur.right
cur.right.next = cur.next.left if cur.next else None
cur_nodes = list(nex_nodes)
def list_create_BinaryTree(s,i):
if i<len(s):
if s[i]=='#':
return None
else:
root = TreeNode(s[i])
root.left = list_create_BinaryTree(s,2*i+1)
root.right =list_create_BinaryTree(s,2*i+2)
return root
return
# root = list_create_BinaryTree('1234567',0)
# bt = BinaryTree(root)
# bt.preOrder()
# print('-------------------------------------')
# bt.inOrder()
# print('-------------------------------------')
# bt.postOrder()
# print('-------------------------------------')
# bt.hierar_travel()
# bt.build_next_pointer()
# print('after bulid next pointer')
# bt.hierar_travel()
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
