柳小葱的力扣之路——树的遍历-6ren

柳小葱的力扣之路——树的遍历

转载作者：知者更新时间：2024-03-13 09:16:30

♦️今天我们来学习树的遍历，这几道题，主要涉及的树的遍历有前、中、后遍历和层序遍历，今天我们来看看几道题，对往期内容感兴趣的同学可以查看👇:

链接: 柳小葱的力扣之路——动态规划详解.

🍭今天我们主要讲中序遍历，因为中序遍历和二叉搜索树有着很大的联系，应用较为广泛，当然我也会演示如何实现前、后序遍历和层序遍历。

1. 前、中、后序遍历

1.1 力扣94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。
输入：root = [1,null,2,3]
输出：[1,3,2]

题解（2种方式）

第一种，我们采用递归的方式，左右子树分别递归，进行中序遍历
第二种，我们采用栈的方式，根节点的左节点不为空，则押入栈中，直到左节点为空，出栈，接着判断该节点的右节点是否存在左子树，依次循环。

#1. 递归实现中序
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        if not root:#递归结束条件
            return res
        #左支
        res.extend(self.inorderTraversal(root.left))#写在类里要加self.
        #中间节点
        res.append(root.val)
        #右支
        res.extend(self.inorderTraversal(root.right))
        return res
       
#2. 栈实现中序
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
            stack=[]
            res=[]
            #当栈内有节点或根节点不为空，则继续循环。
            while stack or root:
            #节点不为空时一直找左子树最左边的元素。
                while root:
                    stack.append(root)
                    root=root.left
                #找到后出栈加入数组作为第一个元素
                root=stack.pop()
                res.append(root.val)
                #然后看该节点是否有右支。
                root=root.right
            return res

在这道题中，我们顺便说一下递归方式实现二叉树的前序和后续遍历。（其实就是换一下位置）

#前序遍历
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        if not root:#递归结束条件
            return res
        #中间节点
        res.append(root.val)
         #左支
        res.extend(self.inorderTraversal(root.left))#写在类里要加self.
        #右支
        res.extend(self.inorderTraversal(root.right))
        return res


#后续遍历
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        if not root:#递归结束条件
            return res
        #左支
        res.extend(self.inorderTraversal(root.left))#写在类里要加self.
        #右支
        res.extend(self.inorderTraversal(root.right))
        #中间节点
        res.append(root.val)
        return res

1.1 力扣98. 验证二叉搜索树

根据树的遍历，我们顺势可以做完下面这道题：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

这道题我们换个角度想，既然要验证是否为有效二叉树，那就是该树的中序遍历是一个严格递增的序列，问题就变成只要判断该树的中序遍历是否严格递增即可。

题解（2种方式）

根据中序遍历的结果进行判断
在中序遍历的过程中进行判断

#方法一：对中序遍历的结果进行升序排列，如果升序前和升序后结果一样，就为true
def isValidBST(self, root: TreeNode) -> bool:
        def midorder(root):#中序遍历部分
            res=[]
            if not root:
               return []
            res.extend(midorder(root.left))
            res.append(root.val)
            res.extend(midorder(root.right))
            return res
        result=midorder(root)#返会中序遍历的对象
        a=result[:]#这里是用a保留一份result的副本
        result.sort()#result排序
        if len(set(a))!=len(result):#中序排序如果有重复元素则为fales
            return False
        if result==a:#如果中序排序的结果和升序排序一样，则为true
            return True
        else:#否则为false
            return False

#方法二：在中序遍历的过程中进行判断是否是升序
def isValidBST(self, root: TreeNode) -> bool:
        stack=[]
        inorder=float('-inf')
        #上部分的中序遍历
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right
        return True

2. 层序遍历

来到层序遍历，和前中后遍历方式不一样的地方在于，一个是树的广度遍历，一个是数的深度遍历。

2.1 力扣 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

题解

这里的解题思路是将每层的节点放入队列中，然后每次输出该层节点个数的队列元素即可。这里有个技巧就是在将节点出队列的过程中，也将该节点的左右节点加入队列进行下一层的遍历。

def levelOrder(self, root: TreeNode) -> List[List[int]]:
	res=[]
	queue=[root]
	if not root:#根节点为空，直接返回[]
		return res
	#队列不为空时
	while queue:
		n=len(queue)
		alist=[]
		for i in range(n):#遍历该层个数的节点
			node=queue.pop(0)
			alist.append(node.val)
			#同时加入下一层的左右节点。
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		res.append(alist)
	resturn res

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

这道题是不是和上面普通的层序遍历很像呢？大家可以思考一下哦，给点提示：从如何实现奇数偶数层不同方向遍历开始。

题解

# 利用计时器来判断遍历到哪一层了。
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res=[]
        queue=[root]
        j=1#初始化计数器j
        if not root:
            return res
        while queue:
            alist=[]
            l=len(queue)
            for i in range(l):
                node=queue.pop(0)
                alist.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            if j%2==1:#奇数层正常遍历
                res.append(alist)
            else:#偶数层返回遍历的逆序
                alist.reverse()
                res.append(alist)
            j+=1#层数+1
        return res