python:二叉树的递归遍历之前序遍历文字详解(基于力扣)
目录
前言:
这篇作为自己“理解二叉树递归”的记录,非常适合和我一样的新手朋友。
二叉树:
关于二叉树,我总结了下面几点:
1. 二叉树和链表相似(这里只说单链表),链表有一个指针,指向下一个节点。
2. 二叉树的每一个节点有两个指针,分别指向左右子节点。
3. 我们所说的“根节点”,并不是但指最顶端的节点,每一个节点,都是根节点。
4. 请务必区分开,根节点的左右指针,指的是“子节点”,还是“左子树”,还是“右子树”。
5. 二叉树的遍历分为三种,分别是:前、中、后序遍历,“前中后”的位置,指的是“根节点”的位置,即:根左右,左根右,左右根。
6. 请牢记第3条tip。
这里为大家避个雷。
在b站上看了一个视频,这个up主讲了一下什么是前中后序遍历,他在遍历的时候,先写出了第一层和第二层的子节点,然后依照递归遍历的方法,在这三个节点左右两边开始加“左右子节点”。说实话,这个视频非常误导我的思路。他的书写方法很好懂,但和递归遍历没有关系。也就是说,看完了,也没整明白怎么递归。
千万不要用上面的思维去理解递归!!!
这是一个手绘二叉树。
前序遍历:
牢记:根左右
我们输出结果,需要有一个列表,于是创建一个空列表result = []
leetcode 建议在类中创建一个 def __init__(self): 函数,初始化这个空列表。
(如果没有初始化,则不会清空result,相当于每次调用的结果都会装在这个列表里)
接下来,遍历开始:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.result = []
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root != None:
self.result.append(root.val)
self.preorderTraversal(root.left)
self.preorderTraversal(root.right)
return self.result
else:
return self.result
黄色高亮表示已经执行了的部分!
1. 第一个遍历头节点:3(是根节点,放到空列表里)————遍历3的左子树————遍历3的右子树。
(注意,3的左子树有一大坨,右子树也有一大坨,按顺序遍历,来到第二步,遍历3的左子树,头一个开刀的即3的左子节点,此时3的左子节点为根节点,来到第2步)(注意!!此时还没有轮到遍历3的右子树)
result = [3]
2. 遍历5 :5(是根节点,放到空列表里)——5的左子树——5的右子树。
(5的左子树也是一大坨,5的右子树也是一大坨,所以继续遍历5的左子节点,此时5的左子节点为根节点)(依然没有轮到右子树)
result = [3, 5]
3. 遍历:8 (是根节点,放到空列表里)——8的左子树——8的右子树
欸,发现,8没有左子树,没有右子树,这段函数完成,回溯至上一节点(5),进行右子树的遍历。
result = [3, 5, 8]
4. 遍历5的右子树:5(是根节点,放到空列表里)——5的左子树——5的右子树。
result = [3, 5, 8, 2]
5. 遍历2:2 (是根节点,放到空列表里)——2的左子树——2的右子树
欸,发现,2没有左子树,没有右子树,那就可以返回result了。
result = [3, 5, 8, 2]
6. 此时,值为 5 的节点已经走完全部三步, 回溯至上一节点(2),完成2的右子树的遍历
result = [3, 5, 8, 2]
7. 回到头节点,遍历右子树:3(是根节点,放到空列表里)————遍历3的左子树————遍历3的右子树。
result = [3, 5, 8, 2]
8. 值为3的节点的右子树中,第一个节点为7:继续重复之前的步骤:
7(是根节点,放到空列表里)————遍历7的左子树————遍历7的右子树。
发现7的左节点为None,于是进行下一步,遍历7的右子树
result = [3, 5, 8, 2, 7]
result = [3, 5, 8, 2, 7]
9. 遍历7的右子树:7(是根节点,放到空列表里)————遍历7的左子树————遍历7的右子树。
右子树只有一个节点6,值放在result里,继续遍历的时候发现左右子节点为None,整个函数执行完毕,回溯至上一节点
result = [3, 5, 8, 2, 7, 6]
10. 此时,整个二叉树遍历完成,输出结果,结果为:
result = [3, 5, 8, 2, 7, 6]