[94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=problem-list-v2&envId=tree)
```python=
class TreeNode:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
def build_tree(values):
root = TreeNode(values[0])
queue = [root]
i = 1
while i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] != None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] != None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
root = [1,"null",2,3]
for i in range(len(root)):
if root[i] == "null":
root[i] = None
rot = build_tree(root)
def mid(root):
if root == None:
return []
return mid(root.left) + [root.val] + mid(root.right)
print(mid(rot))
```
[144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/)
```python=
ro = [1,2,3,4,5,"null",8,"null","null",6,7,9]
for i in range(len(ro)):
if ro[i] == "null":
ro[i] = None
rot = buildtree(ro)
def forward(ro):
if ro == None:
return []
return [ro.val] + forward(ro.left) + forward(ro.right)
print(forward(rot))
```
[145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
```python=
ro = [1,2,3,4,5,"null",8,"null","null",6,7,9]
for i in range(len(ro)):
if ro[i] == "null":
ro[i] = None
rot = buildtree(ro)
def forward(ro):
if ro == None:
return []
return forward(ro.left) + forward(ro.right) + [ro.val]
print(forward(rot))
```
[100. 相同的树](https://leetcode.cn/problems/same-tree/description/?envType=problem-list-v2&envId=tree)
```python=
def istree(p,q):
if not p and not q:
return True
elif not p or not q:
return False
if p.val != q.val:
return False
return istree(p.left,q.left) and istree(p.right,q.right)
root1 = buildtree([1,2,3])
root2 = buildtree([1,2,3])
print(istree(root1,root2))
```
[101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/description/?envType=problem-list-v2&envId=tree)
```python=
def istree(p,q):
if not p and not q:
return True
elif not p or not q:
return False
if p.val != q.val:
return False
return istree(p.left,q.right) and istree(p.right,q.left)
root1 = buildtree([1,2,2,None,3,None,3])
print(istree(root1.left,root1.right))
```
[104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=problem-list-v2&envId=tree)
```python=
def dfs(node):
if node == None:
return 0
lh = dfs(node.left)
rh = dfs(node.right)
return 1 + max(lh,rh)
root = dfs([3,9,20,null,null,15,7]])
print(dfs(root))
```
[111. 二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/)
```python=
def dfs(node):
if node == None:
return 0
if not node.left and not node.right:
return 1
if not node.left:
return dfs(node.right) + 1
if not node.right:
return dfs(node.left) + 1
return min(dfs(node.left),dfs(node.right)) + 1
root = buildtree([1,2,3,4,5])
print(dfs(root))
```
[102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=problem-list-v2&envId=tree)
```python=
def dfs(root):
if not root:return []
result = []
queue = [root]
while queue:
z = []
for i in range(len(queue)):
k = queue.pop(0)
z.append(k.val)
if k.left:
queue.append(k.left)
if k.right:
queue.append(k.right)
result.append(z)
return result
root = buildtree([3,9,20,None,None,15,7])
print(dfs(root))
```
[993. 二叉树的堂兄弟节点](https://leetcode.cn/problems/cousins-in-binary-tree/submissions/)
```python=
def dfs(root,x,y):
if not root:
return
death = 1
queue = [[root,None]]
h1,h2,p1,p2 = 0,0,0,0
while queue:
for i in range(len(queue)):
k,parent = queue.pop(0)
if k.val == x:
p1 = parent
h1 = death
if k.val == y:
p2 = parent
h2 = death
if k.left:
queue.append([k.left,k])
if k.right:
queue.append([k.right,k])
death += 1
return h1 == h2 and p1 != p2
root = buildtree([1,2,3,None,4,None,5])
x = 5;y = 4
print(dfs(root,x,y))
```
[112. 路径总和](https://leetcode.cn/problems/path-sum/description/?envType=problem-list-v2&envId=tree)
```python=
def dfs(root,su):
if root == None:
return False
queue = [[root,root.val]]
while queue:
node,k = queue.pop()
if node.left == None == node.right and k == su:
return True
if node.left:
queue.append([node.left,k + node.left.val])
if node.right:
queue.append([node.right,k + node.right.val])
return False
print(dfs(rot,t))
```
[226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/description/?envType=problem-list-v2&envId=tree)
```python=
def dfs(root):
if root == None:
return []
result = [root.val]
queue = [root]
while queue:
k = queue.pop(0)
if k.right != None:
queue.append(k.right)
result.append(k.right.val)
if k.left != None:
queue.append(k.left)
result.append(k.left.val)
return result
return dfs(root)
```
[257. 二叉树的所有路径](https://leetcode.cn/problems/binary-tree-paths/description/?envType=problem-list-v2&envId=tree)
```python=
result = []
def bfs(node,s):
if node == None:
return
s += str(node.val)
if node.left == node.right == None:
result.append(s)
else:
s += "->"
bfs(node.left,s)
bfs(node.right,s)
bfs(rot,"")
print(result)
```
[404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/description/?envType=problem-list-v2&envId=tree)
```python=
def dfs(node):
if node is None:
return 0
if node.left and node.left.left is None and node.left.right is None:
return node.left.val + dfs(node.right)
return dfs(node.left) + dfs(node.right)
print(dfs(rot))
```
501. 二叉搜索树中的众数
```python=
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(node, val):
if node is None:
return TreeNode(val)
if val <= node.val:
node.left = insert(node.left, val)
elif val >= node.val:
node.right = insert(node.right, val)
return node
z = [1,None,2,2,3,None,3]
root = TreeNode(z[0])
for i in range(1, len(z)):
if z[i] != None:
insert(root, z[i])
def dfs(root):
if not root:
return []
result = {}
queue = [root]
while queue:
z = []
for i in range(len(queue)):
k = queue.pop(0)
if k.val not in result:
result[k.val] = 1
else:
result[k.val] += 1
if k.left:
queue.append(k.left)
if k.right:
queue.append(k.right)
return result
li = dfs(root)
c = [];c1 = [];l =[]
for i, j in li.items():
c.append(i)
c1.append(j)
ma = max(c1)
for i in range(len(c1)):
if c1[i] == ma:
l.append(c[i])
print(l)
```
[面试题 04.08. 首个共同祖先](https://leetcode.cn/problems/first-common-ancestor-lcci/description/?envType=problem-list-v2&envId=depth-first-search)
```python=
# 低效率版
result = []
def bfs(node,s,va):
if node == None:
return
s += str(node.val)
if node.val == va:
result.append(s)
return
else:
bfs(node.left,s,va)
bfs(node.right,s,va)
bfs(rot,"",p)
bfs(rot,"",q)
ma = 0
for i in range(len(result[0])):
if result[0][i] == result[1][i]:
ma = result[1][i]
else:
break
print(ma)
```
樹的直徑
```python=
n = int(input())
adj = [[] for i in range(n+1)]
bol = [True] + [False for i in range(n)]
for i in range(n-1):
a,b = map(int,input().split())
adj[a].append(b)
bol[b] = True
p = bol.index(False)
def dfs(s):
ans = 0
for i in adj[s]:
ans = max(ans,dfs(i)+1)
return ans
if len(adj[p]) == 1:
print(dfs(p))
else:
print(1 + dfs(adj[p][0]))
print(1 + dfs(adj[p][1]))
```
Sign in with Wallet
Connect another wallet