繁依Fanyi0

这个屌丝很懒，什么也没留下！

热门标签

Leetcode树专题_leetcode树状结构

作者：繁依Fanyi0 | 2024-07-05 01:55:57

踩

leetcode树状结构

文章目录

- 前中后序遍历
完全二叉树节点个数(Leetcode222)

#树的常识
##三种遍历方法

深度遍历包括前中后序遍历三种；
广度优先遍历就是层次遍历。
PS：
前中后序遍历，如果使用递归遍历，都很简单易理解；
如果使用非递归方式，首先想到的就应该是使用栈结构来控制整个过程，因为递归也是利用栈来实现的；
前中后序遍历的非递归方式中，后序遍历的非递归方式相比较而言，略复杂。

四种主要的遍历思想为：
前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点（后序遍历需要用到2个栈，和其他两种遍历很不一样，需要有这个敏感性！）
层次遍历：只需按层次遍历即可

##对应的数据结构
深度优先遍历：栈
广度优先遍历：队列

前中后序遍历

我以前从没意识到树的前中后序遍历写法是不同的
我以前惯用的写法其实是前序遍历，但这是最简单的
中序遍历思路：
输出是左根右。求的思路是一直访问左子节点，当左子节点没有的时候，返回父节点访问右子节点。
后序遍历思路：
要用两个栈，思路是求左->右->根，那么只要按根->右->左的顺序放到栈#2里，栈#2弹出来的时候就是左右根了。然后我们再构造栈#1，由于把根节点不经过栈1直接放入栈2，所以栈1的弹出顺序需要是右->左，栈1的入栈顺序就必须是左->右（可以写出来了，类比前序遍历第一种方法）

class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

nodea=Node("A")
nodeb=Node("B")
nodec=Node("C")
noded=Node("D")
nodee=Node("E")
nodef=Node("F")
nodeg=Node("G")

nodea.lchild=nodeb
nodea.rchild=nodec
nodeb.lchild=noded
nodeb.rchild=nodee
nodec.rchild=nodef

#后序遍历：左右根 #DEBFCA
def houxubianli(root):
    if root==None:
        return
    stack_1=[]
    stack2_reverse_houxubianli=[]
    stack_1.append(root)
    while stack_1:#当stack1不为空
        currentnode=stack_1.pop()
        if currentnode.lchild:#如果左孩子不为空
            stack_1.append(currentnode.lchild)
        if currentnode.rchild:
            stack_1.append(currentnode.rchild)
        stack2_reverse_houxubianli.append(currentnode)

    while stack2_reverse_houxubianli:
        print(stack2_reverse_houxubianli.pop().data)
print("后序遍历结果：")
houxubianli(nodea)

#前序遍历 根左右#A应该是ABDECF
def qianxubianli(root):
    if root == None:
        return
    stack=[root]
    while stack:9
        currentnode=stack.pop()
        print(currentnode.data)
        if currentnode.rchild:
            stack.append(currentnode.rchild)
        if currentnode.lchild:
            stack.append(currentnode.lchild)

print("前序遍历结果：")
qianxubianli(nodea)

#中序遍历 左根右 应该是DBEACF
def zhongxubianli(root):
    if root==None:
        return
    stack=[]
    while root or stack:#当栈不为空的时候
        if root:
            stack.append(root)
            root=root.lchild
        else:
            root=stack.pop()
            print(root.data)
            root=root.rchild
print("中序遍历结果：")
zhongxubianli(nodea)
#前序遍历第二种方法
def qianxubianli_2(root):
    if root == None:
        return
    stack = []
    while root or stack:
        while root:  # 从根节点开始，一直找它的左子树
            print(root.data)
            stack.append(root)
            root = root.lchild  # while结束表示当前节点为空，即前一个节点没有左子树了
        root = stack.pop()
        root = root.rchild  # 开始查看它的右子树
print("前序遍历第二种方法:")
qianxubianli_2(nodea)
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
81
82
83
84
85
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
81
82
83
84
85

输出结果是:

后序遍历结果：
D
E
B
F
C
A
前序遍历结果：
A
B
D
E
C
F
中序遍历结果：
D
B
E
A
C
F
前序遍历第二种方法:
A
B
D
E
C
F

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
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

##阿里面试题：如何确保广度优先遍历的时候一层已经遍历完了？
https://www.cnblogs.com/simplepaul/p/6721687.html
可以参见文中技巧1和技巧2

#Leetcode257.Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/
2 3

5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
##思路：很典型的深度优先搜索配合栈，宽度优先搜索配合队列。学一个遍历二叉树的方法

# dfs + stack（这其实是前序遍历，用栈）
def binaryTreePaths1(self, root):
    if not root:
        return []
    res, stack = [], [(root, "")]
    while stack:
        node, ls = stack.pop() #node=root, ls=" "
        if not node.left and not node.right:
            res.append(ls+str(node.val))
        if node.right:
            stack.append((node.right, ls+str(node.val)+"->"))
        if node.left:
            stack.append((node.left, ls+str(node.val)+"->"))
    return res
    
# bfs + queue 层次遍历用队列
def binaryTreePaths2(self, root):
    if not root:
        return []
    res, queue = [], collections.deque([(root, "")])
    while queue:
        node, ls = queue.popleft()
        if not node.left and not node.right:
            res.append(ls+str(node.val))
        if node.left:#这句话如果和下一句 if node.right分支调换顺序结果也是一样的
            queue.append((node.left, ls+str(node.val)+"->"))
        if node.right:
            queue.append((node.right, ls+str(node.val)+"->"))
    return res
    
# dfs recursively，递归
def binaryTreePaths(self, root):
    if not root:
        return []
    res = []
    self.dfs(root, "", res)
    return res

def dfs(self, root, ls, res):
    if not root.left and not root.right:
        res.append(ls+str(root.val))
    if root.left:
        self.dfs(root.left, ls+str(root.val)+"->", res)
    if root.right:
        self.dfs(root.right, ls+str(root.val)+"->", res)
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
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

#Leetcode111. Minimum Depth of Binary Tree（求二叉树的最短深度）
学会这道题的套路以后就会做很多事了，比如下面这道题:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

72ms打败89.59%的python3答案

##较差的思路：从上题思路套用而来，先求得所有路径的节点数（就是长度），再求最小值

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

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
      
        if not root:  
            return 0  
        res, stack = [], [(root,1)]  
        while stack:  
            node, length = stack.pop() #node=root  
            if not node.left and not node.right:  
                res.append(length)  
            if node.right:  
                stack.append((node.right, length+1))  
            if node.left:  
                stack.append((node.left, length+1))  
        return min(res)  
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
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

##较好的思路：宽度优先搜索那就是用广度优先搜索！
套用第一题的套路得到如下运行了69ms打败了94.57%python3答案的solution:

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

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        res, queue = [], collections.deque([(root, 1)])
        while queue:
            node, ls = queue.popleft()
            if not node.left and not node.right:
                return ls #这里是重点，这里返回相当于返回了最小值，避免了不必要的遍历操作
            if node.left:
                queue.append((node.left, ls+1))
            if node.right:
                queue.append((node.right, ls+1))
   
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
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

#Leetcode104.剑指OFFER面试题55 Maximum Depth of Binary Tree(二叉树的深度)
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

69ms 81.30%/73.91%的python3用户的solution:
##较差的思路1：深度优先搜索，以tuple形式存储每个节点的深度

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

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:  
            return 0  
        res, stack = [], [(root,1)]  
        while stack:  
            node, length = stack.pop() #node=root  
            if not node.left and not node.right:  
                res.append(length)  
            if node.right:  
                stack.append((node.right, length+1))  
            if node.left:  
                stack.append((node.left, length+1))  
        return max(res)  
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
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

##较差的思路2
看到一个更好的做法，65ms，这样不用把（节点，当前节点对应的深度（就是路径上的节点数））以tuple的形势存储。
这种做法我理解为宽度优先搜索

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

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        count = 0
        queue = [root]
        while queue:
            count += 1
            next_lvl = []
            for node in queue:
                if node.left:
                    next_lvl.append(node.left)
                if node.right:
                    next_lvl.append(node.right)
            queue = next_lvl
        return count
        
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
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

##较好的思路（剑指OFFER思路）：递归
跑了55ms,和python3 45ms的解法同思路

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

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#Leetcode662. Maximum Width Of Binary Tree（阿里面试题，广度优先搜索）
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:
Input:

       1
     /   \
    3     2
   / \     \  
  5   3     9 
1
2
3
4
5

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input:

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:

      1
     / \
    3   2
   /     \  
  5       9 
 /         \
6           7
1
2
3
4
5
6
7

Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Note: Answer will in the range of 32-bit signed integer.
##较好的思路
The main idea in this question is to give each node a position value. If we go down the left neighbor, then position -> position * 2; and if we go down the right neighbor, then position -> position * 2 + 1. This makes it so that when we look at the position values L and R of two nodes with the same depth, the width will be R - L + 1.

反思面试：
面试官描述题目的时候并没有提到空节点怎么算（不像这道题目描述的这么严谨，他可能就是在等我问他），面试官问我听明白了吗？我说听明白了。我想当然地以为是完全二叉树，没有考虑过如果一层里有空节点的话，那么该层的宽度怎么算。

我先说出了用广度优先遍历，遍历完每层记录宽度，再对宽度求最大值的思路。

面试官问我如何确保一层遍历完了？
我回答维护一个队列，在把左右孩子添加进去之前求该队列的长度，就是当前层的宽度。

其实我觉得我回答的没错，但是面试官显然还是不满意，他说希望能在空间还是时间上进行优化来着？忘了记不清了

现在想想他是不是在提示我用tuple的形式把每个节点和它所在的层次一块存储

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

class Solution(object):
    def widthOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        queue = [(root, 0, 0)]
        cur_depth = left = ans = 0
        for node, depth, pos in queue:
            if node:
                queue.append((node.left, depth+1, pos*2))
                queue.append((node.right, depth+1, pos*2 + 1))
                if cur_depth != depth:
                    cur_depth = depth
                    left = pos
                ans = max(pos - left + 1, ans)

        return ans
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
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

根据104题的这第二种做法，我们又可以完成求每层的平均值，如下题：
#Leetcode637. Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:

Input:
3
/
9 20
/
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:

The range of node’s value is in the range of 32-bit signed integer.

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

class Solution:
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        if not root:  
            return 0   
        queue = [root]  
        res=[root.val]
        while queue:  
            next_lvl_node = []
            next_lvl_total=0#记录每层值的和
            for node in queue:  
                if node.left:  
                    next_lvl_node.append(node.left)
                    next_lvl_total=next_lvl_total+node.left.val
                if node.right:  
                    next_lvl_node.append(node.right)
                    next_lvl_total=next_lvl_total+node.right.val
            if len(next_lvl_node)!=0:#如果下一层有元素存在,注意这里必须用个数判断，不能用current_lvl_total!=0去判断
                res.append(next_lvl_total/len(next_lvl_node))
            queue=next_lvl_node    
        return res
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
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

这个答案119ms.

#Leetcode112.Path Sum
##（按照257的深度优先搜索方法改编的解法）

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

打败了大概35%的用户

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:  
            return False  
        res, stack = [], [(root,0)]  #存基准值
        while stack:  
            node, ls = stack.pop() #node=root, ls=" "  
            if not node.left and not node.right:  
                res.append(ls+node.val)  
            if node.right:  
                stack.append((node.right, ls+node.val))  
            if node.left:  
                stack.append((node.left, ls+node.val))
        
        return sum in res
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
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

改进一点,有符合的路径的时候立即停止运行程序：

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:  
            return False  
        res, stack = [], [(root,0)]  #存基准值
        while stack:  
            node, ls = stack.pop() #node=root, ls=" "  
            if not node.left and not node.right:  
                if(ls+node.val )==sum:
                    return True
            if node.right:  
                stack.append((node.right, ls+node.val))  
            if node.left:  
                stack.append((node.left, ls+node.val))
        
        return False
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
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

62ms,打败了40.97%,和最快的48s解法的思想是一样的

#Leetcode113.Path Sum II
##思路：按照257的深度优先搜索方法改编的解法，题意:寻找路径和为给定值的所有路径

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ \ /
7 2 5 1
return

[
[5,4,11,2],
[5,8,4,5]
]

我的原创解法：

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

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res, stack = [], [(root, [],0)]#初值，可以理解为占位用，代表类型
        while stack:
            node, ls,total = stack.pop() #node=root, ls=" "
            if not node.left and not node.right:
                res.append([ls+[node.val],total+node.val])
            if node.right:
                stack.append((node.right,ls+[node.val],total+node.val))
            if node.left:
                stack.append((node.left, ls+[node.val],total+node.val))
        
        return [result[0]  for result in res if result[1]==sum]
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
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

但是这个解法非常慢，125ms,打败了2.01%的python解法。
于是我看了看别人的答案发现可能是return的时候写了个for循环导致了没有必要的遍历，浪费了时间。于是改进成如下：69ms,打败了60%~70%+的python submission

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

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res, stack = [], [(root, [],0)]#初值，可以理解为占位用，代表类型
        while stack:
            node, ls,total = stack.pop() #node=root, ls=" "
            if not node.left and not node.right and (total+node.val)==sum:
                    res.append(ls+[node.val])
            if node.right:
                stack.append((node.right,ls+[node.val],total+node.val))
            if node.left:
                stack.append((node.left, ls+[node.val],total+node.val))
        
        return res
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
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

#Leetcode404. Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.

Example:

3
/
9 20
/
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

##思路：分类讨论
按左child是叶子还是树讨论

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

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
                
        if not root: return 0
        if root.left and not root.left.left and not root.left.right:#左子树不是树，是叶子
            return root.left.val + self.sumOfLeftLeaves(root.right)
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)#左子树不是叶子，是树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#Leetcode572. (剑指OFFER面试题26）Subtree of Another Tree （树的子结构）

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

3
/
4 5
/
1 2
Given tree t:
4
/
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

3
/
4 5
/
1 2
/
0
Given tree t:
4
/
1 2
Return false.

从Leetcode的举例来看，我们能明白这题和剑指OFFER上的题还不完全一样，isSubTree这个主函数是一样的，判断两棵树是否相同的函数DoesSHasT不一样。
剑指OFFER：S包含T即可，S的所有后代T不必完全都拥有，只要T这棵树在S这棵树中能找到即可。
LEETCODE：S包含T，S的所有后代T都必须完全拥有！
由于题意的不同，所以函数DoesSHasT也相应地改动了退出递归的判断条件。

##剑指OFFER官方思路

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

class Solution(object):
    def isSubtree(self, s, t):
        """
        判断t是不是s的子树（s的所有孩子t都得一模一样）
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def DoesSHasT(s,t):
            """
            判断两棵树的结构是否完全一样
            """
            if t==None and s!=None:#t遍历完了，而S没遍历完，说明s的结构比t大，所以二者不完全一样
                    return False 
            if t==None and s==None:#t和s都遍历完了，说明二者一样
                    return True
            if t!=None and s==None:#t没遍历完，s遍历完了，说明s的结构比t小，所以二者不完全一样
                    return False
            #注意以上这些判断条件和剑指OFFER不同，因为需求改了
            if s.val!=t.val:
                return False
            
            return DoesSHasT(s.left,t.left)and DoesSHasT(s.right,t.right)
                
     
        result=False
        if(s!=None and t!=None):#其实本题已经说了是两棵非空树了，为了保持与剑指Offer一致还是做一下鲁棒性处理
                if s.val==t.val:
                #如果两棵树根节点相等，再往下判断有没有相同子结构；如果根节点的值都不相等，则result仍为False,往下进行
                    result=DoesSHasT(s,t)
                if result==False:
                    result=self.isSubtree(s.left,t)
                if result==False:#注意每一次都要重新判断result的布尔值
                    result=self.isSubtree(s.right,t)
        return result
        
       
          
            
            

        
        
        
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
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

##我认为更好写的思路：通过中左右这样的中序遍历把t树和s树转换为字符串，判断t字符串是否在s字符串里（借鉴自该题某discussion）

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

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
 
       def convert(p):
            return "^" + str(p.val)  + convert(p.left) + convert(p.right) if p else "$"
        
        return convert(t) in convert(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

理解“^{”在这里的目的，比如s是单节点树12,t是单节点树2，那么如果不加“}”，则会返回True,因为2在12里，但实际t并不在s里；所以加上“^{”以后防止了这种情况，因为}2不在^12里，符合t不在s里的事实。
这种做法跑了115ms,打败了89%的用户。

完全二叉树节点个数(Leetcode222)

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input:
1
/
2 3
/ \ /
4 5 6

Output: 6

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

class Solution:
    def countNodes(self, root):
        leftdepth = self.getdepth(root, True)
        rightdepth = self.getdepth(root, False)

        if leftdepth == rightdepth:
            return 2 ** leftdepth - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def getdepth(self, root, isLeft):
        if root is None:
            return 0
        if isLeft:
            return 1 + self.getdepth(root.left, isLeft)
        else:
            return 1 + self.getdepth(root.right, isLeft)
        
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
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/788852