要求在现有代码上修改,正确的返回前序遍历
```python
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self,val=None):
self.root = TreeNode(val)
def insertLeft(self, item):
node = TreeNode(item)
if self.root.left is None:
self.root.left = node
else:
t = node
t.left = self.root.left
self.root.left = t
def insertRight(self, newitem):
node = TreeNode(newitem)
if self.root.right == None:
self.root.right = node
else:
t = node
t.right = self.root.right
self.root.right = t
def getLeftchild(self):
return self.root.left
def getRightchild(self):
return self.root.right
def getRootVal(self):
return self.root.val
def preorderTraversal(self):
if not self.root:
return []
# 前序递归
return [self.root.val] + self.preorderTraversal(self.getLeftchild()) + self.preorderTraversal(self.getRightchild())
#深度算法
def depth(self):
if __name__ == '__main__':
b = Solution('A')
b.insertLeft('a')
b.insertRight('b')
print(b.preorderTraversal())
```
#二叉树
class TreeNode:
def __init__(self, x, left=None, right = None):
self.val = x
self.left = left
self.right = right
tree = TreeNode('A',TreeNode('B',TreeNode('D',TreeNode('H')),TreeNode('E',None,TreeNode('I'))), TreeNode('C',TreeNode('F'),TreeNode('G')))
class Traversal:
# 前序遍历(根节点->前序遍历左子树->前序遍历右子树)
def preorderTraversal(self, root):
res = []
if root is None:
return []
def preorder(tmp_tree):
if tmp_tree.left is None and tmp_tree.right is None: # 当左右子树不存在是,说明该分支遍历到底部
res.append(tmp_tree.val) # 将当前节点加入res
return
res.append(tmp_tree.val) # 加入根节点
if tmp_tree.left is not None: # 当左子树不为空是,继续前序遍历左子树
tmp_tree_new = tmp_tree.left # 生成前序遍历的左子树
preorder(tmp_tree_new) # 对新的子树递归调用前序遍历
if tmp_tree.right is not None: # 左子树为空,根节点加入res,继续中前序遍历右子树
tmp_tree_new = tmp_tree.right # 生成前序遍历的右子树
preorder(tmp_tree_new) # 对新的子树递归调用前序遍历
preorder(root)
return res
traversalor = Traversal()
print('前序遍历结果为:', traversalor.preorderTraversal(tree))
参考 https://blog.csdn.net/u011517132/article/details/103599858
在现有代码上修改,代码如下:(如有帮助,望采纳!谢谢! 点击我这个回答右上方的【采纳】按钮)
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self,val=None):
self.root = TreeNode(val)
def insertLeft(self, item):
node = TreeNode(item)
if self.root.left is None:
self.root.left = node
else:
t = node
t.left = self.root.left
self.root.left = t
def insertRight(self, newitem):
node = TreeNode(newitem)
if self.root.right == None:
self.root.right = node
else:
t = node
t.right = self.root.right
self.root.right = t
def getLeftchild(self,t="root"):
if t=="root":
t = self.root
return t.left
def getRightchild(self,t="root"):
if t=="root":
t = self.root
return t.right
def getRootVal(self,t="root"):
if t=="root":
t = self.root
return t.val
def preorderTraversal(self,t="root"):
if t=="root":
t = self.root
if not t:
return []
# 前序递归
return [t.val] + self.preorderTraversal(self.getLeftchild(t)) + self.preorderTraversal(self.getRightchild(t))
#深度算法
def depth(self):
pass
if __name__ == '__main__':
b = Solution('A')
b.insertLeft('a')
b.insertRight('b')
print(b.preorderTraversal())
二叉树的前中后序遍历,无非是在递归时,改变下
取值+左子树递归+右子树递归的顺序
可以参考这个,详细理解下这部分概念
https://blog.csdn.net/u013834525/article/details/80421684 https://blog.csdn.net/u013834525/article/details/80421684
如果有帮助,点个采纳谢谢