chapter9-tree-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 7.1k | Reading time ≈ 33

chapter9-tree-algorithm

[TOC]

树算法

递归
1. 树的高度

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 深度搜索，直接遍历完全部的节点，直到叶子节点为空时，返回，每返回一层，就加1
    # 由于用left和right两种节点，所以需要判断最大深度
    def maxDepth(self, root: TreeNode) -> int:
        if not  root:
            return 0
        return max(self.maxDepth(root.right)+1,self.maxDepth(root.left)+1)
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
# s = Solution()
# print(s.maxDepth(root))
2. 平衡树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution1:

    # you题意可知
    # 1. 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
    # 因此用深度搜索遍历左右两个子节点，直到为None
    # 注意返回应是求树的深度一样，只不过是从叶子节点开始计数
    # 因此每次返回当前节点中，左右节点最多的数
    # 如果不满足规则1，就返回False
    # 代码逻辑如下：
    def __init__(self):
        self.result = True

    def maxDepth(self, root: TreeNode) -> bool:
        if not root:
            return 0
        l = self.maxDepth(root.left)
        r = self.maxDepth(root.right)
        if abs(l-r) > 1:
            self.result = False
        return 1 + max(l, r)

    def isBalanced(self, root: TreeNode) -> bool:
        self.maxDepth(root = root)
        return self.result

# s = Solution1()
# print(s.isBalanced(root))
3. 两节点的最长路径

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution2:

    # 遍历每一个节点的深度(深度搜索)
    # 知道为None时，返回+1即为当前几点数
    # 由于每一个节点数，等于左右子节点数字和
    # 返回过程中，每次记录当前节点最大路径
    # 代码逻辑如下：
    def __init__(self):
        self.result = 0

    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        l = self.maxDepth(root.left)
        r = self.maxDepth(root.right)
        self.result = max(self.result, l + r)
        return 1 + max(l, r)

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.maxDepth(root)
        return self.result

# s = Solution2()
# print(s.diameterOfBinaryTree(root))
4. 翻转树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution3:

    # you题意可知
    # 利用深度优先搜索，遍历到叶子节点
    # 返回时，每次交换左右节点即可（当前层）
    # 代码逻辑如下：
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        left = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(left)
        return root
# s = Solution3()
# s.invertTree(root)
5. 归并两棵树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution4:

    # you题意可知
    # 合并两棵树
    # 1. 如果两个节点重叠，那么将他们的值相加作为节点合并后的新值
    # 2. 不为 NULL 的节点将直接作为新二叉树的节点
    # 简单点说，合成那颗树的结点等于两棵树节点值的和（没有结点值为0）
    # 因为是同层同方向结点相加，因此直接同时深度搜索两棵树即可
    # 返回值是每次新建结点
    # 利用上一层结点'指向'当前节点之和，这样就能够形成新的结点了
    # 注意是到了每一棵树结点为None开始返回
    # 返回值为当前节点，类型TreeNode
    def mergeTrees( self, t1: TreeNode, t2: TreeNode ) -> TreeNode:
        if not t1 and not t2:
            return None
        if not t1:
            return t2
        if not t2:
            return t1
        root = TreeNode(t1.val+t2.val)
        root.left = self.mergeTrees(t1.left, t2.left)
        root.right = self.mergeTrees(t1.right, t2.right)
        return root

t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)

t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.right = TreeNode(3)
t2.left.right = TreeNode(4)
t2.right.right = TreeNode(7)

s = Solution4()
s.mergeTrees(t1, t2)
6. 判断路径和是否等于一个数

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution5:
    # 深度向下搜索树的每一给节点
    # 每次用目标值，减去节点
    # 知道当无子节点，且当前值，等于当前目标值时，返回True
    # 如果遍历完全 没有，则返回False
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        # 这样就直接遍历最后一层，不会在往下。
        if not root.right and not root.left and sum == root.val:
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

t5 = TreeNode(5)
t5.left = TreeNode(4)
t5.right = TreeNode(8)
t5.left.left = TreeNode(11)
t5.left.left.left = TreeNode(7)
t5.left.left.right = TreeNode(2)
t5.right.left = TreeNode(13)
t5.right.right = TreeNode(4)
t5.right.right.right = TreeNode(1)

s = Solution5()
print(s.hasPathSum(t5, 22))
7. 统计路径和等于一个数的路径数量

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution6:
    def __init__(self):
        self.result = 0

    # you题意可知
    # 1.找出路径和等于给定数值的路径总数。
    # 2.路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）
    # 因此注意：
    # 1. 它可以从任何节点开始，任何节点结束
    # 2. 亦有了起点，必须和终点连续(父节点指向子节点)，中间不可切断
    # 因此递归代码逻辑就有了：
    # 1. 因为每一个节点都可能为起点，所以递归所有的点，进行遍历
    # 2. 因为有了起点后，必须是连续的，所以再一次深度搜索遍历子下节点，判断节点之和是否有等于所给数值
    # 因此代码如下：
    def pathNum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        if sum == root.val:
            self.result += 1
        self.pathNum(root.left, sum - root.val)
        self.pathNum(root.right, sum - root.val)


    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root :
            return 0
        self.pathNum(root,sum)
        self.pathSum(root.left,sum)
        self.pathSum(root.right, sum)
        return self.result


    # 递归的实现很简单，就是全部结果都进行遍历，但是时间复杂度较高，而且两个递归方法
    # 分析递归可知
    # 深度遍历每一个节点是必要的(上述第二次递归)
    # 但对于递归每一个起点是没有必要的
    # 我们可以利用‘动态规划’思想。进行保存‘过程’，已经遍历节点的和，字典存储dp
    # 当前节点的和-目标值，且这个值存在于字典dp当中，那么说明这连续值是可以成立的。
    # 因为是从上往下遍历，所以能够保证分析每一个节点作为起点的类别
    # 由于在一颗数当中，左右节点是不连续的，所以需要回溯
    # 就是当遍历完节点为None，返回上一个节点，需要把dp的值也要跟新为上一个值的结果
    # 因此代码逻辑如下：
    def pathNum1(self, root: TreeNode, s: int,dp: {0:1}, curSum: int ) -> int:
        if not root:
            return 0
        curSum += root.val
        os = curSum - s
        if os in dp:# 判断历史值
            self.result += dp[os]
        if curSum == s:# 判断当前值
            self.result += 1
        dp[curSum]  = dp.get(curSum,0)+1 # 一定是先判断(都还没和，如果有历史)，后加入前缀和，防止只有[1,0] sum=0的siller
        self.pathNum1(root.left, s, dp, curSum)
        self.pathNum1(root.right, s, dp, curSum)
        dp[curSum] -= 1

    def pathSum1(self, root: TreeNode, sum: int) -> int:
        self.result = 0
        if not root:
            return 0
        self.pathNum1(root, sum,{}, 0)
        return self.result


t6 = TreeNode(10)
t6.left = TreeNode(5)
t6.right = TreeNode(-3)
t6.left.left = TreeNode(3)
t6.left.right = TreeNode(2)
t6.left.left.left = TreeNode(3)
t6.left.left.right = TreeNode(-2)
t6.left.right.right = TreeNode(1)
t6.right.right = TreeNode(11)

s = Solution6()
print(s.pathSum(t6, 8))
print(s.pathSum1(t6, 8))
8. 子树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution7:

    # you题意可知
    # 1. 因为是子数，子树中的起点可能是父树中的每一个点，所以直接一层递归
    # 2. 如何判断是否相等
    # 两棵树同时遍历，同时判断左右子节点值，是否有相等即可
    # 如果其中一个遍历完，还要另一个节点是否遍历完，如果没有False，因为叶子节点也必须相同
    def isS(self,s, t):
        if not t and not s:
            return True
        if not t or not s:
            return False
        if t.val != s.val:
            return False
        return self.isS(t.left, s.left) and self.isS(t.right, s.right)

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        return self.isS(s,t) or self.isSubtree(s.right, t) or self.isSubtree(s.left, t)

t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.right = TreeNode(3)
t2.left.right = TreeNode(4)
t2.right.right = TreeNode(7)
9. 树的对称

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution8:
    # you题意可知
    # 思路和求子树一样
    # 只不过是一棵树分为两棵树，然后进行判断
    # 左右两个字树，同层深度遍历。判断是否对称即可
    def isS(self,s, t):
        if not t and not s:
            return True
        if not t or not s:
            return False
        if t.val != s.val:
            return False
        return self.isS(t.left, s.right) and self.isS(t.right, s.left)


    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.isS(root.right,root.left)

t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)

# s = Solution8()
# print(s.isSymmetric(t1))
10. 最小路径

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution9:

    # you题意可知
    # 最小路径及当深度遍历树时，一到叶子节点，就进行返回，因为此时的深度是最小的
    # 由于一开始就有左右两条路径，所以需要判断最终谁小
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        if left == 0 or right == 0:
            return left + right + 1
        return min(left, right) + 1
t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)

s = Solution9()
# print(s.minDepth(t1))
11. 统计左叶子节点的和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution10:
    # 深度遍历所有的做节点
    # 如果做节点是，叶子节点，则返回累加值
    # 代码逻辑如下：

    # 判断是否是叶子节点
    def isLeaf(self, node):
        if not node:
            return False
        return not node.right and not node.left

    def sumOfLeftLeaves(self, root: TreeNode) -> int:
            if not root:
                return 0
            if self.isLeaf(root.left) :
                return root.left.val + self.sumOfLeftLeaves(root.right)
            return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)

s = Solution10()
# print(s.sumOfLeftLeaves(t1))
12. 相同节点值的最大路径长度

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution11:
    def __init__(self):
        self.paths = 0


    # you题意可知
    # 1. 路径中的每个节点具有相同值
    # 因此深度遍历树时，判断返回值，下一个节点是否相等，如果相等着路径加1
    # 需要注意的是，如果连接同一个节点，左右分支如果数值相同，他也属于同一个路径
    # 因此代码如下：
    def ls(self, root):
        if not root:
            return 0
        left = self.ls(root.left)
        right = self.ls(root.right)
        print(55,root.val)
        if root.left != None and root.left.val == root.val:
            leftPath = left + 1
        else:
            leftPath = 0
        if root.right != None and root.right.val == root.val:
            rightPath = right + 1
        else:
            rightPath = 0

        self.paths = max(self.paths, leftPath + rightPath)
        return max(leftPath, rightPath)

    def longestUnivaluePath(self, root: TreeNode) -> int:

        self.ls(root)
        return self.paths

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)
# t6.left.left.left = TreeNode(1)
# t6.left.left.right = TreeNode(1)
# t6.left.right.right = TreeNode(1)
# t6.right.right = TreeNode(1)

s = Solution11()
# print(s.longestUnivaluePath(t6))
13. 间隔遍历

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution12:

    # 暴力求解
    # you题意可知
    # 小偷在偷类似二叉树的房子过程中
    # 以层为单位（树的深度），相邻层是不能偷的
    # 所以以每一个节点为起点，每次移动两步进行求和
    # 代码逻辑如下：
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        val2 = self.rob(root.left) + self.rob(root.right)
        return max(val1, val2)



    # 由于上诉代码。
    # 遍历一颗数是，对于多个递归，当深度逐渐升高，遍历重复部分越来越多
    # 因此可以使用临时存储，记录已经遍历过的结点，及时返回
    def rob1(self, root):
        dp = {}
        def dfs(root):
            nonlocal dp
            if not root: return 0
            if root in dp:
                return dp[root]
            val1 = root.val
            if root.left:
                val1 += self.rob(root.left.left) + self.rob(root.left.right)
            if root.right:
                val1 += self.rob(root.right.left) + self.rob(root.right.right)
            val2 =  max(val1, self.rob(root.left) + self.rob(root.right))
            dp[ root ] = val2
            return  val2
        res = dfs(root)
        print(res)
        return res

    # 小偷在偷的过程中只在乎偷与不偷
    # 对于每层来说也是只在乎报警与不报警
    # 因此对于小偷来说，要使得结果最大
    # 就是在当前层对于下一层的判断
    # 即为：
    # 1、如果偷这一层价值=当前节点价值+上一层左右节点不偷的价值
    # 2、如果不偷这一层价值=上一层左右节点价值最大值之和
    # 因为是深度搜索，当遍历到最后叶子节点开始返回
    # 比如当前遍历到最左下节点，那么的价值就等于0，因为不管偷与不偷，他下一层的价值是没有的
    # 对于他的父节点。就依据上述规则1，2
    # 即代码逻辑如下：
    def rob2(self, root: TreeNode) -> int:

        def dfs(root):
            if not root:
                return 0,0
            #val1 不偷 val2 偷
            lval1, lval2 = dfs(root.left)
            rval1, rval2 = dfs(root.right)
            val1 = max(lval1, lval2) + max(rval1, rval2)
            val2 = root.val + rval1 + lval1

            return val1, val2

        return max(dfs(root))


t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)

s = Solution12()
print(s.rob2(t6))
14. 找出二叉树中第二小的节点

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution13:

    # you题意可知
    # 直接规律可言
    # 每次遍历最小的值，知道结束
    # 而最第二节点的值即为当前节点
    # 如果两个结点都大于父节点，那么就是当前兄弟节点中最小的结点
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        if not root:
            return -1
        if not root.left and not  root.right:
            return -1
        leftVal = root.left.val
        rightVal = root.right.val
        if leftVal == root.val:
            leftVal = self.findSecondMinimumValue(root.left)
        if rightVal == root.val:
            rightVal = self.findSecondMinimumValue(root.right)
        if leftVal != -1 and rightVal != -1:
            return min(rightVal, leftVal)
        if leftVal != -1:
            return leftVal
        return rightVal
层次遍历
1. 一棵树每层节点的平均数

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution14:
    def averageOfLevels( self, root: TreeNode ):
        # you题意可知
        # 我们需要一层一层遍历，就广度优先遍历
        # 对于深度搜索算法适应与栈，广度优先搜索算法适应与队列
        # 因此我们只需要一个队列存储一层的结点，输出的时候，
        # 在计算这一层的累加值时，同时加入当前节点的子节点(这一子节点就是下一层的结点)
        # 便于好理解，我们使用两个队列一个记录当前层的结点，一个记录下一层的结点
        # 代码逻辑如下：

        import queue
        def slove1():
            if not root:
                return 0
            dpq1 = queue.Queue()
            dpq2 = queue.Queue()
            res= []
            dpq1.put(root)
            while(not dpq1.empty() or not dpq2.empty()):
                sc = []
                if not dpq1.empty():
                    while(not dpq1.empty()):
                        p = dpq1.get()
                        if  p.right:
                            dpq2.put(p.right)
                        if  p.left:
                            dpq2.put(p.left)
                        sc.append(p.val)
                elif not dpq2.empty():
                    while (not dpq2.empty()):
                        p = dpq2.get()
                        if  p.right:
                            dpq1.put(p.right)
                        if  p.left:
                            dpq1.put(p.left)
                        sc.append(p.val)
                res.append(sum(sc)/len(sc))
            return res

        # 对于两个队列，我们是没有用到先进先出队列的特点的
        # 对于当前层来说，我们能够算出，当前层的结点数
        # 我们只需要抛出当前节点数即可，每次抛出，我们都把子节点加入末尾
        # 由于只遍历当前节点的数，所以后面加入的节点是遍历不到的(后面加入的节点，属于后进后出)
        # 因此代码逻辑如下：
        def slove2():
            res, dpq = [], queue.Queue()
            dpq.put(root)
            while(not dpq.empty()):
                sc = 0
                dl = dpq.qsize()
                for i in range(dl):
                    p = dpq.get()
                    if p.left: dpq.put(p.left)
                    if p.right:dpq.put(p.right)
                    sc += p.val
                res.append(sc/dl)

            return res
        return slove2()


t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)

s = Solution14()
print(s.averageOfLevels(t6))
2. 得到左下角的节点

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution15:
    # you题意可知
    # 利用广度优先搜索，一层一层遍历
    # 每一层遍历完都是最右或者最左的一个结点
    # 此，需要找出最左下角的结点，因此，我们直接先搜索树的右结点
    # 从右到左，遍历完后，最后一个结点，就是最左下角的结点了
    # 代码如下：

    def findBottomLeftValue(self, root: TreeNode) -> int:
        import queue
        dpq = queue.Queue()
        dpq.put(root)
        while(not dpq.empty()):
            root = dpq.get()
            if root.right:dpq.put((root.right))
            if root.left: dpq.put(root.left)

        return root.val

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)

s = Solution15()
print(s.findBottomLeftValue(t6))
前中后序遍历
3. 非递归实现二叉树的前序遍历

Leetcode / 力扣

4. 非递归实现二叉树的后序遍历

Leetcode / 力扣

5. 非递归实现二叉树的中序遍历

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution16:

    # you题意可知
    # 使用栈后进先出的原则
    # 每次输出父节点，然后依次加入右节点和左节点(后进先出)
    # 直到遍历完为止：
    # 代码逻辑如下：
    def preorderTraversal(self, root: TreeNode):
        if not root:
            return 0
        prer = []
        stack = [root]
        while(stack):
            node = stack.pop()
            if not node:
                continue
            prer.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
        return prer

    # 后序遍历
    # 和前序思路一样，利用栈后进先出的原则，先遍历右节点即可
    # 需要注意的是，由于想要输出根去去左右节点
    # 对于根左右取反=右左根
    def postorderTraversal( self, root: TreeNode ):
        stack, res = [root], []
        while(stack):
            node = stack.pop()
            if not node:
                continue
            res.append(node.val)
            stack.append(node.left)
            stack.append(node.right)
        return res[::-1]

    # 中序遍历
    # 直接遍历到最左节点
    # 注意的是需要遍历根后，加入右结点
    # 由于最后一个结点是没有叶子节点的，所以它就是根节点
    def inorderTraversal( self, root: TreeNode ):
        stack, res = [  ], [ ]
        node = root
        while (node or stack):
            while node:
                stack.append(node)
                node = node.left
            cur = stack.pop()
            res.append(cur.val)
            node = cur.right
        return res

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.right.left = TreeNode(21)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)

s = Solution16()
print(s.inorderTraversal(t6))
BST
1. 修剪二叉查找树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution17:

    # you题意可知
    # 在[L,R]的范围类
    # 通过观察，小于L的结点，都是左节点，因此这个结点你不要了，下面的结点只能挂在他父节点的右结点
    # 同理，大于R的结点，都是右节点，因此这个结点你不要了，下面的结点只能挂在他父节点的左结点
    # 如果这两个结点都没有了，直接返回到上一层
    # 因此代码逻辑如下：
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        # 2. if语句进行判断返回的内容，以及所属到那个结点上
        if not root:
            return None
        if root.val < L:
            return self.trimBST(root.right, L, R) #
        if root.val > R:
            return self.trimBST(root.left, L, R)
        #1. 先遍历完全部结点
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)

        return root

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(2)
t6.right.left = TreeNode(21)
t6.left.left = TreeNode(1)
t6.left.right = TreeNode(1)

s = Solution17()
s1 = Solution16()
print(s1.inorderTraversal(s.trimBST(t6, 2, 22)))
2. 寻找二叉查找树的第 k 个元素

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution18:
    def __init__(self):
        self.res = 0
        self.cnt = 0

    # 中序遍历方法
    # 求出第k个元素即可
    # 非递归方法
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        if not root:
            return 0
        stack = []
        cur = root
        while(cur or stack):
            while(cur):
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            cur = node.right
    # 递归方法
    # 需要全局或者类变量进行计数
    # 然后返回第k个元素
    def kthSmallest1(self, root: TreeNode, k: int) -> int:
        if not root:
            return
        self.kthSmallest1(root.left, k)
        self.cnt += 1
        if self.cnt == k:
            self.res = root.val
            return root.val
        self.kthSmallest1(root.right,k)


t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(4)
t6.left.right = TreeNode(2)
s = Solution18()
print(s.kthSmallest1(t6, 1))
3. 把二叉查找树每个节点的值都加上比它大的节点的值

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution19:

    # you题意可知
    # 观察树的结构，
    # 树的做右的结点是最大的，最左节点是最小的
    # 因此只需要从右根左顺序去遍历这个树
    # 用全局变量去累加值
    # 然后每次返回，把当前节点改为累加值即可
    # 因此代码逻辑如下：
    def __init__(self):
        self.sum =0

    def traver(self, root):
        if not root:
            return 0
        self.traver(root.right)
        self.sum += root.val
        root.val =self.sum
        self.traver(root.left)


    def convertBST(self, root: TreeNode) -> TreeNode:
        self.traver(root)
        return root
t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(4)
t6.left.right = TreeNode(2)
s = Solution19()
print(s.convertBST(t6))
4. 二叉查找树的最近公共祖先

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution21:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        # 有题意可知 最近
        # 什么是查找树：就是左子节点<=根节点<=右子节点
        # 因此，对于查找最近公共祖先来说
        # 通过判断当前值与p,q进行判断，可以指定方向查找，这样更快，规则如下：
        # 1. 当前值都大于p和q，说明这两个值一定在左叶子节点下
        # 2. 当前值都小于于p和q，说明这两个值一定在右叶子节点下
        # 3. 当前值都大于等于或者小于等于，或者一大一小等，那么公共祖先就是当前值
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root
5. 二叉树的最近公共祖先

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution20:

    # you题意可知
    # 找两个节点的公共祖先
    # 如果遍历到了当前公共祖先，说明祖先一定在上面或者本身。就返回当前值
    # 如果遍历完一条枝丫，那直接返回None，说明这两个节点不在这条枝丫上
    # 因此就有有以下情况
    # 1. 如果有一条枝丫遍历完为None，没有找到其中一个结点。说明找到的那个结点一定就是那个结点的祖先，因为另一个结点，在这个结点之下，即为他的子孙
    # 2. 如果两个节点都有值，说明两个节点不在同一个枝丫上，那他的公共祖先就是最上面的根节点
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right,p, q)
        if not left:
            return right
        elif not right:
            return left
        else:
            return root

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(4)
t6.left.right = TreeNode(2)
s = Solution20()
print(s.lowestCommonAncestor(t6,t6.right,t6.left).val)
6. 从有序数组中构造二叉查找树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution22:


    # you题意可知
    # 二叉查找树，在满足平衡树的前提下
    # 还需要满足左子节点<=根节点<=右子节点
    # 因此，利用二分法，去选择有序数组中点，与左右树进行建立三点枝丫
    # 因此代码逻辑如下：
    def toBST(self, nums, left, right):
        if left > right:
            return

        mid = left + (right - left)//2
        root = TreeNode(nums[mid])
        root.left = self.toBST(nums, left, mid - 1)
        root.right = self.toBST(nums, mid +1, right)
        return root

    def sortedArrayToBST(self, nums: []) -> TreeNode:
        return  self.toBST(nums, 0, len(nums) - 1)

s = Solution22()
s.sortedArrayToBST([-10,-3,0,5,9])
7. 根据有序链表构造平衡的二叉查找树

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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

class Solution23:
    # you题意可知
    # 同理与从“有序数组中构造二叉查找树”
    # 之间也可以相互转换，只是数组变为链表，还是可以通过二分法，用下标表示
    # 这里主要通过指针去二分链表，但逻辑同理
    # 1. 去链表的中值建为根节点，左右分别建立树的左右节点
    # 2. 因为只有这样才会满足二叉查找树的左子节点<=根节点<=右子节点特点
    # 难点：
    # 1. 如何找链表的中值(利用快“每次走两步“指针和慢指针“每次走一步“的特点，就能够找出中值)
    # 2. 如何去把链表分为两部分(找到中值后，中值左边放入用head，而右边用中值mid，
    #  因为在找到中值时，可以记录中值的前一个点，把它与中值断开，这样就把链表分为独立的两部分)
    # 3. 当取到最后一个值是，也就是下个值为空时，就可以直接返回为树节点了

    def preMid( self, head: ListNode ):
        # 使用慢指针和快指针就行求链表的中值
        slow, fast = head, head
        pre = None
        while (fast and fast.next):
            pre = slow
            slow = slow.next
            fast = fast.next.next

        pre.next = None
        return slow

    def sortedListToBST( self, head: ListNode ) -> TreeNode:
        if not head: return None
        if not head.next: return TreeNode(head.val)
        mid = self.preMid(head)
        t = TreeNode(mid.val)
        t.left = self.sortedListToBST(head)
        t.right = self.sortedListToBST(mid.next)
        return t

lt = ListNode(0)
lt.next = ListNode(3)
s = Solution23()
print(s.sortedListToBST(lt))
7. 在二叉查找树中寻找两个节点，使它们的和为一个给定值

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution24:

    # 利用中序遍历得到有序数组
    # 然后通过二指针方法，找出目标值即可
    # 代码逻辑如下：
    def __init__(self):
        self.dp = []

    def iv(self,root):
        if not root:
            return
        self.iv(root.left)
        self.dp.append(root.val)
        self.iv(root.right)

    def findTarget(self, root: TreeNode, k: int) -> bool:
        self.iv(root)
        print(self.dp)
        left, right = 0, len(self.dp) - 1
        while(left < right):
            if self.dp[left] + self.dp[right] == k:
                return True
            if self.dp[left] + self.dp[right] > k:
                right -= 1
            else:
                left += 1
        return False
8. 在二叉查找树中查找两个节点之差的最小绝对值

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution25:

    # you题意可知
    # 要两点之间绝对值最小（两点有序数之间绝对值最小--依次遍历去最终最小）
    # 由于是二叉查找树（中序遍历有序）
    # 因此代码逻辑如下：
    def __init__( self ):
        self.dp = [ ]
        self.preNode = None
        self.minv = float('-inf')

    def iv( self, root ):
        if not root:
            return
        self.iv(root.left)
        self.dp.append(root.val)
        self.iv(root.right)

    def getMinimumDifference( self, root: TreeNode ) -> int:
        # self.iv(root)
        # print(self.dp)
        # minv = float('inf')
        # for i in range(1, len(self.dp)):
        #     minv = min(minv, self.dp[i] - self.dp[i-1])
        # return minv
        self.inOrder(root)
        return self.minv

    def inOrder( self, root: TreeNode ) -> int:
        if not root:
            return
        self.inOrder(root.left)
        if self.preNode != None:
            self.minv = min(self.minv, root.val - self.preNode)
        self.preNode = root.val
        print(root.val, self.preNode)
        self.inOrder(root.right)
9. 寻找二叉查找树中出现次数最多的值

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution26:
    # you题意可知
    # 二叉查找树(中序遍历遍历有序)
    # 找出现次数最多的值(中序遍历，相等的值连续)
    # 因此，中序遍历，记录前一个值，判断是否和当前值相等，如果相等计数
    # 并且通过与当前最大值比较，是否记录当前值
    # 代码逻辑如下
    def __init__(self):
        self.maxv = float('-inf')
        self.preNode = None
        self.cnt = 1
        self.num = []

    def inOrder(self, root):
        if not root:
            return
        self.inOrder(root.left)
        if self.preNode != None:
            if root.val == self.preNode:
                self.cnt += 1
            else:
                self.cnt = 1
        self.preNode = root.val

        if self.cnt == self.maxv:
            self.num.append(root.val)
        elif self.cnt > self.maxv:
            self.maxv = self.cnt
            self.num = []
            self.num.append(root.val)
        self.inOrder(root.right)

    def findMode( self, root: TreeNode ):
        self.inOrder(root)
        print(self.num)
        return self.num

t6 = TreeNode(11)
t6.left = TreeNode(1)
t6.right = TreeNode(4)
t6.left.right = TreeNode(2)
s = Solution26()
print(s.findMode(t6))
Trie
1. 实现一个 Trie

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

class Node:
    def __init__( self ):
        self.childs = [0]*26
        self.isLeaf = False

class Trie:

    # you题意可知
    # 实现前缀树(一种存储字符串的多叉树结构的树)
    # 简单来说：
    # 根节点没有值
    # 下面节点的当前值new一个存储26个字母的空间，进行存储字符的第一个字符和一个标志是否是末尾值，也就是标志这字符串有没有
    # 下面结构一致
    # 层数 看你所插入字符串的长度的多少
    # 代码逻辑结果如下：

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def indexForChar(self, c):
        return ord(c) - ord('a')

    def insert1(self, word, node):
        if not node:
            return
        if len(word) == 0:
            node.isLeaf = True
            return
        index = self.indexForChar(word[0])
        if not node.childs[index]:
            node.childs[index] = Node()
        self.insert1(word[1:], node.childs[index])


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        self.insert1(word, self.root)


    def search1(self, word, node):
        if not node:
            return False
        if len(word) == 0:
            return node.isLeaf
        index = self.indexForChar(word[0])
        return self.search1(word[1:], node.childs[index])

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        return self.search1( word, self.root)

    def startWith1(self,prefix, node):
        if not node:
            return False
        if len(prefix) == 0:
            return True
        index = self.indexForChar(prefix[0])
        return self.startWith1(prefix[1:],node.childs[index])

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        return self.startWith1(prefix, self.root)



# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert('word')
param_2 = obj.search('word')
print(param_2)
2. 实现一个 Trie，用来求前缀和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Node:
    def __init__( self ):
        self.childs = [None]*26
        self.value = 0


class MapSum:

    #
    def __init__( self ):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def indexForChar(self, c):
        return ord(c) - ord('a')

    def insert1(self, key, val, node):
        if not node:
            return
        if len(key) == 0:
            node.value = val
            return
        index = self.indexForChar(key[0])
        if not node.childs[index]:
            node.childs[ index ] = Node()
        self.insert1(key[1:],val, node.childs[index])


    def insert( self, key: str, val: int ) -> None:
        self.insert1(key, val, self.root)

    def sum1(self,prefix, node):
        if not node:
            return 0
        # 找到此前缀下，最后一个字母的Node节点
        if len(prefix) != 0:
            index = self.indexForChar(prefix[0])
            return self.sum1(prefix[1:], node.childs[index])
        # 对求和全部字符串的健值
        # 广度遍历搜索Node节点，一层一层求和
        # 知道节点为空位置
        s = node.value
        for c in node.childs:
            s += self.sum1(prefix, c)
        return s


    def sum( self, prefix: str ) -> int:
        return  self.sum1(prefix, self.root)


# Your MapSum object will be instantiated and called as such:
obj = MapSum()
obj.insert('apple',3)
obj.insert('app',3)
obj.insert('appl',3)
obj.insert('applee',3)
param_2 = obj.sum('app')
print(param_2)