(1)二叉树的遍历

# 1.中序遍历:
# -->走左边-->记录-->走右边
# 遍历BST非递减

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        return [i for i in inorder(root)]

#关于yield,next的使用

#找到BST中第k小的元素:
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        it =inorder(root)
        for i in range(k):
            ans=next(it)
        return ans


# 2.前序遍历:
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(node):
            if node:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)
        return [i for i in preorder(root)]


# 3. 后序遍历
# 3.1 N叉树后序遍历
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        def f(node):
            if node:
                for i in node.children: yield from f(i)
                yield node.val
        return [i for i in f(root)]

(2)112. 路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root: return False
        sum-=root.val
        if not root.left and not root.right :
            return sum==0
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

(3)113.路径总和II

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。

class Solution:
    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
        if not root :return []
        stack=[([root.val],root)]
        ans=[]
        while stack:
            val,node=stack.pop()
            if not node.left and not node.right and sum(val)==sum_:
                ans.append(val)
            if node.left:
                stack.append((val+[node.left.val],node.left))
            if node.right:
                stack.append((val+[node.right.val],node.right))
        return ans

# 方法二:回溯法
class Solution:
    def pathSum(self, root: TreeNode, k: int) -> List[List[int]]:
        ans=[]
        def bk(node,path,k):
            if not node: return
            path.append(node.val)
            if k==node.val and not node.left and not node.right: 
                ans.append(path[:])
            bk(node.left,path,k-node.val)
            bk(node.right,path,k-node.val)
            path.pop()
        bk(root,[],k)
        return ans

(4)437.路径总和III

给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root: return 0
        return self.dfs(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)
    def dfs(self,root,path):
        if not root: return 0
        path-=root.val
        return (1 if path==0 else 0)+self.dfs(root.left,path)+self.dfs(root.right,path)

(5)翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        def invert(root):
            if not root: return 
            root.left,root.right=root.right,root.left
            invert(root.left)
            invert(root.right)
        invert(root)
        return root

(6)二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        ans=[]
        def dfs(node,depth):
            if not node: return 
            if len(ans)==depth:
                ans.append([node.val])
            else:
                ans[depth].append(node.val)
            dfs(node.left,depth+1)
            dfs(node.right,depth+1)
        dfs(root,0)
        return [sum(i)/len(i) for i in ans]

(7)相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p==None and q==None: return True
        if p==None or q==None: return False
        if p.val!=q.val: return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) 

(8)二叉树的深度

# 最大深度
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        else:
            left_height=self.maxDepth(root.left)
            right_height=self.maxDepth(root.right)
        return max(left_height,right_height)+1

# 最小深度
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        self.ans=float('inf')
        def dfs(node,depth):
            if depth>self.ans: return 
            if not node.left and not node.right:
                self.ans=min(self.ans,depth)
                return
            if node.left: dfs(node.left,depth+1)
            if node.right: dfs(node.right,depth+1)
        dfs(root,1)
        return self.ans

(9)左叶子之和

计算给定二叉树的所有左叶子之和。

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        self.ans=0

        def dfs(node):
            if not node: return 
            if node.left and node.left.val and (not node.left.left) and (not node.left.right):
                self.ans+=node.left.val
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return self.ans

#左叶子没有子节点

(10)二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。
["1->2->5", "1->3"]的类型表示

说明: 叶子节点是指没有子节点的节点。

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        ans=[]
        if not root: return ans
        def dfs(node,path):
            path+=str(node.val)
            if not node.left and not node.right: ans.append(path)
            if node.left: dfs(node.left,path+"->")
            if node.right: dfs(node.right,path+"->")
        dfs(root,"")
        return ans

(11)恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        nodes=[]      
        def dfs(root):    #中序遍历
            if not root: return 
            dfs(root.left)
            nodes.append(root)
            dfs(root.right)
        dfs(root)

        pre=nodes[0]
        x,y=None,None
        for i in range(1,len(nodes)):
            if pre.val > nodes[i].val:
                y=nodes[i]
                if not x: x=pre  # x为第一个出错的位置
            pre=nodes[i]   #准备下一次遍历
        if x and y: 
            x.val, y.val=y.val, x.val
#说明: 
# 空间复杂度O(n)
# 那个常数空间的莫里斯遍历不懂
# 在这种遍历情况下,二叉搜索树的值从小到大

(12)二叉树展开为链表

给定一个二叉树,原地将它展开为一个单链表。
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        cur=root
        while cur:
            if cur.left:
                p=cur.left    #向左子树移动
                while p.right: p=p.right #找到root左子树的最右节点
                p.right=cur.right #将root右子树连到找到的节点
                cur.right=cur.left #再移回来
                cur.left=None
            cur=cur.right

(13)二叉搜索树中的众数

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        ans=[]
        cnt,max_cnt,last=0,0,None
        for i in inorder(root):
            if i== last: cnt+=1
            else: cnt=1
            if cnt>max_cnt: ans=[i]
            elif cnt==max_cnt: ans.append(i)
            max_cnt=max(max_cnt,cnt)
            last=i
        return ans

# python O(1)的中序遍历

(13)验证BST

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inorder(node):
            if node: 
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        pre=float('-inf')
        for i in inorder(root):
            if i<=pre: return False
            pre=i
        return True 

平衡二叉树

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(root):
            if not root: return 0
            left=dfs(root.left)
            if left==-1: return -1
            right=dfs(root.right)
            if right==-1: return -1
            return max(left,right)+1 if abs(left-right)<=1 else -1      

        return dfs(root)!=-1

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录