---
# System prepended metadata

title: 練習樹

---

[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]))
```