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

x33g5p2x  于2022-02-07 转载在 其他  
字(3.4k)|赞(0)|评价(0)|浏览(293)

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

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

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

1. 前、中、后序遍历

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

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

题解(2种方式)

  1. 第一种,我们采用递归的方式,左右子树分别递归,进行中序遍历
  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种方式)

  1. 根据中序遍历的结果进行判断
  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

3. 参考资料

  • 力扣官网(LeetCode)
  • 算法小抄
  • python数据结构

相关文章