leetcode二叉树

二叉树的中序遍历
验证二叉搜索树
恢复二叉搜索树
相同的树
对称二叉树
二叉树的层序遍历
二叉树的锯齿形层序遍历
二叉树的最大深度
从前序与中序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树
路径总和
路径总和 II
二叉树中的最大路径和
二叉树的下一个节点
树的子结构
二叉树的镜像
从上到下打印二叉树
平衡二叉树
求根节点到叶节点数字之和
打家劫舍 III

树的属性：

层次结构
一个节点的所有子节点独立于另一个节点的子节点。

二叉树：如果树中的每个节点最多有两个子节点，我们说该树是一个二叉树。

1.列表表示的树

在列表树的列表中，将根节点的值存储为列表的第一个元素；第二个元素：一个表示左子树的列表；第三个元素：表示右子树的另一个列表。

2.节点表示

用

left

和

right

的属性表示其他实例的引用。

3 . 树的遍历

前序 ：首先访问根节点，然后递归地做左子树的前序遍历，随后是右子树的递归前序遍历。
中序 ：递归地对左子树进行一次遍历，访问根节点，最后递归遍历右子树。
后序 ：递归地对左子树、右子树进行后序遍历，最后访问根节点。

基于二叉堆的优先队列

在优先级队列中，队列中的项的逻辑顺序由他们的优先级确定。最高优先级项在队列的前面，最低优先级的项在后面。实现优先级队列的经典方法是使用二叉堆的数据结构。二叉堆允许我们在O(logn) 中排队和取出队列。

堆看起来就像一棵树，但当我们实现它时，我们只使用一个单一的列表作为内部表示。二叉堆有两个常见的变体：最小堆（最小的键在前面）和最大堆。

二叉堆的实现

完整二叉树(平衡二叉树)：每一层都有其所有的节点，除了树的最底层，从左到右填充。

父节点的左子节点：2p；右子节点的位置：2p+1

二叉查找树

二叉查找树依赖于在左子树中找到的键小于父节点的属性，并且在右子树中找到的键大于父代。

leetcode 例题练习

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

示例：

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

思路：中序遍历 left–>root–>right, 用递归算法

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        if root ==None:
            return []
        
        # 中序遍历
        res=[]
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
         return res
        # 前序遍历
        return [root.val] +self.preorderTraversal(root.left) + self.preordertraversal(root.right)
        # 后序遍历
        return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]
        
### 迭代法：
class Solution:
    def inorderTraversal(self,root):
        res=[]
        stack=[]
        cur=root
        ## 中序：先用指针找到子树的最左下角
        while stack or cur:
            while cur:          # 节点为空，说明没有左子节点
                stack.append(cur)
                cur=cur.left
            cur=stack.pop()
            res.append(cur.val)
            cur=cur.right
        return res

    ###前序迭代
    def preorderTraversal(self,root):
        stack=[root]
        res=[]
        while stack:
            node=stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
    
    ### 后序遍历
    def postorderTraversal(root):
        res=[]
        stack=[]
        node=root
        while stack or node:
            while node:
                stack.append(node)
                if node.left:
                    node=node.left
                else:
                    node=node.right
            node=stack.pop()
            res.append(node.val)
            if stack and stack[-1].left ==node:           # 栈中不为空，且存在父节点
                node=stack[-1].right                      # 加入兄弟右节点
            else:
                node=None
        return res

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例

输入:
    2
   / \
  1   3
输出: true

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解题思路：利用中序遍历，根据遍历之后的数组是否有序返回True或False

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        res=self.inorderTraversal(root)
        for i in range(len(res)-1):
            if res[i]>=res[i+1]:
                return False
        return True
    def inorderTraversal(self,root):
        if root ==None:
            return []
        res=[]
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
        return res

另一种解法：中序+栈

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        pre = None
        stack = list()
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                if pre and root.val <= pre.val:
                        return False
                
                pre = root
                root = root.right

        return True

99. 恢复二叉搜索树

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

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

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

解题思路：检测中序数列，交换不符合要求的节点

代码如下：

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.pre=None
        self.p1,self.p2=None,None
        self.inorderTraversal(root)
        self.p2.val,self.p1.val=self.p1.val,self.p2.val
    def inorderTraversal(self,root):
        if root:
            self.inorderTraversal(root.left)          # 该步会一直递归到树的最后左子树的叶节点
            if self.pre and self.pre.val>root.val:
                if self.p1==None:
                    self.p1=self.pre
                self.p2=root
            self.pre=root       #将最低左子树赋值
            self.inorderTraversal(root.right)   # 最低树的右子树

100. 相同的树

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

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

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

代码如下：

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None and q ==None:
            return True
        if p == None or q == None:#[1,2][1,null,2]
            return False
        if p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else :
            return False

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分

解题思路：

root为空，则直接返回True。否则递归迭代:

先判断基本情况：

左、右子树均为空
任意一个不为空
左、右子树值不同

如果left.val == right.val ，递归下去，判断(left.left ,right.right) 和（left.right,right.left)是否同样成立。

代码如下：

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.helper(root.left,root.right)
    def helper(self,left,right):
        if left == None and right == None:
            return True
        elif left==None or right ==None:
            return False
        elif left.val !=right.val:
            return False
        else:
            return self.helper(left.left,right.right) and self.helper(left.right,right.left)

### 方法二： 迭代
# 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 isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        import collections
        queue=collections.deque()
        queue.append((root.left,root.right))
        while queue:
            left,right=queue.popleft()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            queue.append((left.left,right.right))
            queue.append((left.right,right.left))
        return True

102. 二叉树的层序遍历

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        from collections import deque    # 广度优先遍历： 队列结构
        if not root:
            return []
        queue=deque()
        queue.append(root)
        res=[]
        while queue:
            cur_level=[]           # 存放当前节点的值
            for _ in range(len(queue)):
                node=queue.popleft()
                cur_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(cur_level)
        return res

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

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack=[root]
        res=[]
        is_even_layer=True
        import collections
        while stack:
            cur_level=collections.deque()           # 双端队列存放当前层的节点值
            nodes=[]                                # 临时栈：存放下一轮的值
            for  q in stack:            # 每轮都把当前层的节点遍历完，并把下一层的节点存放在临时栈中，并重新赋值给循环栈
                if is_even_layer:
                    cur_level.append(q.val)
                else:
                    cur_level.appendleft(q.val)
                if q.left:
                    nodes.append(q.left)
                if q.right:
                    nodes.append(q.right)
            stack=nodes
            is_even_layer= not is_even_layer
            res.append(list(cur_level))
        return res

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

示例：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

方法1 ：递归思想

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

方法2 迭代思想

# 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 maxDepth(self, root: TreeNode) -> int:
        if not root :
            return 0
        from collections  import deque
        queue=deque()
        queue.append((root,1))           # 存放当前的节点值以及根节点到当前节点的深度
        res=0                  
        while queue:
            node,depth=queue.popleft()       # 先进入节点的值
            if node :
                res=max(res,depth)
                queue.extend([(node.left,depth+1),(node.right,depth+1)])
        return res

105. 从前序与中序遍历序列构造二叉树

前序遍历

preorder = [3,9,20,15,7]

中序遍历

inorder = [9,3,15,20,7]

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return 
        root =TreeNode(preorder[0])
        idx=inorder.index(preorder[0])
        root.left=self.buildTree(preorder[1:idx+1],inorder[:idx])
        root.right=self.buildTree(preorder[1+idx:],inorder[idx+1:])
        return root

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。

# 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 hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
        stack=[]
        stack.append((root,root.val))
        while stack:
            node,path=stack.pop(0)
            if not node.left and not node.right and path ==targetSum:
                return True
            if node.left:
                stack.append((node.left,path+node.left.val))
            if node.right:
                stack.append((node.right,path+node.right.val))
        return False

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        res=[]
        self.dfs(root,targetSum,res,[])
        return res
    
    def dfs(self,root,targetSum,res,path):
        if not root:        # 空节点，不做处理
            return 
        if not root.left and not root.right and  root.val==targetSum:
            res.append(path+[root.val])
        self.dfs(root.left,targetSum-root.val,res,path+[root.val])    
        self.dfs(root.right,targetSum-root.val,res,path+[root.val])   # 程序执行完这部分的代码，就表示dfs函数执行完成

124. 二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点

leetcode二叉树

# 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.maxSum = float("-inf")
    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(node):
            if not node :      # 递归边界
                return 0
            # 递归计算左右节点的最大贡献值
            leftGain=max(maxGain(node.left),0)    # 递归调用
            rightGain=max(maxGain(node.right),0)

            # 节点的最大路径和取决于该节点的值与该节点左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain
            self.maxSum = max(self.maxSum, priceNewpath) # 从下往上更新最值

            # 返回当前节点的操作值
            return  node.val + max(leftGain, rightGain) # 返回当前节点的最大贡献值
        maxGain(root)
        return self.maxSum

二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def getNext(self, node):
        # 1. 寻找右子树，如果存在就一直找到右子树的最左边，就是下一个节点
        if node.right:
            tmp = node.right
            while tmp.left:
                tmp = tmp.left
            return tmp
        # 2. 没有右子树，就寻找它的父节点，一直找到它是父节点的左子树，打印父节点
        else:
            while node.next:
                if node.next.left != node:
                    node = node.next
                else:
                    return node.next
            return None

剑指 Offer 26. 树的子结构

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        result=False
        if A and B:
            if A.val==B.val:
                result=self.isequal(A,B)
            if  not result:
                result=self.isSubStructure(A.left,B)
            if not result:
                result=self.isSubStructure(A.right,B)
        return result
    
    def isequal(self,root1,root2):
        if not root2:
            return True
        if not root1:
            return False
        if root1.val !=root2.val:
            return False
        return self.isequal(root1.left,root2.left) and self.isequal(root1.right,root2.right)

剑指 Offer 27. 二叉树的镜像

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

剑指 Offer 32 - I. 从上到下打印二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        result=[]
        stack=[]
        if root ==None:
            return result
        stack.append(root)
        while stack:
            node=stack.pop(0)
            result.append(node.val)
            if node.left!=None:
                stack.append(node.left)
            if node.right!=None:
                stack.append(node.right)
        return result

129. 求根节点到叶节点数字之和

leetcode二叉树

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

方法一：深度优先搜索

思路与算法：

深度优先搜索是很直观的做法。从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

leetcode二叉树

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, prevTotal: int) -> int:
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        return dfs(root, 0)

方法二：广度优先搜索

思路与算法：

使用广度优先搜索，需要维护两个队列，分别存储节点和节点对应的数字。

初始时，将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字，进行如下操作：

如果当前节点是叶子节点，则将该节点对应的数字加到数字之和；
如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应的数字分别加入两个队列。

搜索结束后，即可得到所有叶子节点对应的数字之和。

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0

        total = 0
        nodeQueue = collections.deque([root])
        numQueue = collections.deque([root.val])
        
        while nodeQueue:
            node = nodeQueue.popleft()
            num = numQueue.popleft()
            left, right = node.left, node.right
            if not left and not right:
                total += num
            else:
                if left:
                    nodeQueue.append(left)
                    numQueue.append(num * 10 + left.val)
                if right:
                    nodeQueue.append(right)
                    numQueue.append(num * 10 + right.val)

        return total

337. 打家劫舍 III

class Solution:
    def rob(self, root: TreeNode) -> int:
        def DFS(root):
            if not root:
                return 0, 0
            # 后序遍历
            leftchild_steal, leftchild_nosteal = DFS(root.left)
            rightchild_steal, rightchild_nosteal = DFS(root.right)

            # 偷当前node，则最大收益为【偷当前节点+不偷左右子树】
            steal = root.val + leftchild_nosteal + rightchild_nosteal
            # 不偷当前node，则可以偷左右子树
            nosteal = max(leftchild_steal, leftchild_nosteal) + max(rightchild_steal, rightchild_nosteal)
            return steal, nosteal
            
        return max(DFS(root))

leetcode二叉树

目录

继续阅读

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

【数据结构】医院选址

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希