二叉树自定义栈前中后序遍历，层序遍历，N叉树遍历，打印二叉树所有路径
1、二叉树前中后遍历
二叉树前中后遍历推荐使用自定义栈进行解题，不要使用递归解题，栈中的元素没有null元素
中序遍历思路：
- 先将全部的左子节点入栈
- 弹出栈顶元素item
- 指针cur指向item右子节点
前序或后序遍历思路：
- 栈顶节点弹栈，把当点节点value加入到result中
- 左右子节点分别入栈，注意出栈顺序需要保证对应的遍历顺序（前序入栈：中左右->先右后左；后序入栈：左右中->先右后左）
二叉树中序遍历
leetcode-94
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
cur = root
res = []
while stack or cur:
if cur: # 把所有左侧节点添加到栈中
stack.append(cur)
cur = cur.left
else: # 弹栈，遍历右侧节点
item = stack.pop()
res.append(item.val)
cur = item.right
return res
二叉树前序遍历
leetcode-144
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Definition for a binary tree node.
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack, result = [root], []
while stack:
item = stack.pop()
result.append(item.val)
# 入栈先右后左，保证出栈时的顺序为先左后右
if item.right: stack.append(item.right)
if item.left: stack.append(item.left)
return result
if __name__ == '__main__':
A = TreeNode(1)
B = TreeNode(2)
C = TreeNode(3)
A.left = B
A.right= C
s = Solution()
result = s.preorderTraversal(A)
print(result)
二叉树后序遍历
leetcode-145
from typing import List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack, result = [root], []
while stack:
item = stack.pop()
result.append(item.val)
if item.left: stack.append(item.left)
if item.right: stack.append(item.right)
return result[::-1]
2、N叉树的前序遍历
和二叉树的前序遍历思路基本类似，只是在添加子节点部分略有修改
# Definition for a Node.
from typing import List
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root: return []
stack, result = [root], []
while stack:
item = stack.pop()
result.append(item.val)
if item.children: stack.extend(item.children[::-1])
return result
3、二叉树的所有路径
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
result = []
def dfs(root, path):
if root.left is None and root.right is None: # 子节点
path += str(root.val)
result.append(path)
else:
path += str(root.val)+"->"
if root.left:dfs(root.left,path)
if root.right:dfs(root.right,path)
if root:
dfs(root, "")
return result
4、层序遍历
层序遍历遍历的关键点之一是需要记录队列中的结点数量，用于划分不同的层
4-1 二叉树的深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路：
利用广度优先遍历思想，进行二叉树的层序遍历，每遍历一层深度+1，这道题的确不是很难leetcode上标注的为easy
import queue
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
dep = 0
q = queue.Queue()
q.put(root)
while q.empty() is False:
nodes_len = q.qsize()
for i in range(nodes_len):
node = q.get()
if node.left: q.put(node.left)
if node.right: q.put(node.right)
dep += 1
return dep
4-2 二叉树之字形遍历
原题地址：剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000
解题思路：层序遍历的变形，在偶数层，添加倒序列表，单数层正序列表
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Definition for a binary tree node.
from typing import List
import queue
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# -- BEGIN--
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
"""之字形遍历"""
if root is None: return []
result = []
q = queue.Queue()
q.put(root)
count = 1
level = 1
while not q.empty():
new_count = 0
tmp = []
for _ in range(count):
item = q.get()
tmp.append(item.val)
if item.left is not None:
q.put(item.left)
new_count += 1
if item.right is not None:
q.put(item.right)
new_count += 1
count = new_count
if level % 2 != 0:
result.append(tmp)
else:
result.append(tmp[::-1])
level += 1
return result
# -- END --
if __name__ == '__main__':
A = TreeNode(1)
B = TreeNode(2)
C = TreeNode(3)
D = TreeNode(4)
E = TreeNode(5)
A.left = B
A.right = C
C.left = D
C.right = E
s = Solution()
result = s.levelOrder(A)
print(result)
4-3 序列化二叉树
原题地址：剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
解题思路：利用二叉树的层序遍历，把每一层的节点都放到列表中(包含最后一层)，注意题目中的意思是能够实现序列化和反序列化函数即可，不必在意序列化之后的树的结点列表与所给出的不同。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Definition for a binary tree node.
import collections
from queue import Queue
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Codec:
def serialize(self, root):
"""
二叉树层序遍历
:param root:
:return:
"""
if not root: return "[]"
res = []
q = Queue()
q.put(root)
while not q.empty():
cur = q.get()
if cur:
res.append(str(cur.val))
# 存放下一层节点 none节点也需要存放
q.put(cur.left)
q.put(cur.right)
else:
res.append("null")
return '[' + ','.join(res) + ']'
def deserialize(self, data):
if data == "[]": return
vals, i = data[1:-1].split(','), 1
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
if __name__ == '__main__':
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(4)
e = TreeNode(5)
a.left = b
a.right = c
c.left = d
c.right = e
res = Codec().serialize(a)
print(res)
5、平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
限制：
1 <= 树的结点个数 <= 10000
注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/
解题思路：
二叉树深度的判断和二叉树遍历的结合体，总体思路就是，判断每一个节点的左右子树的最大深度只差不超过1，空节点的深度为0
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def dfs(cur):
# 获取当前节点的左右子树高度
left_dep, right_dep = self.maxDepth(cur.left), self.maxDepth(cur.right)
# 判断左子树是否平衡
left_res = dfs(cur.left) if cur.left else True
# 判断右子树是否平衡
right_res = dfs(cur.right) if cur.right else True
# 最终判断 当前子树平衡并且左右子树平衡当前二叉树才为平衡二叉树
return abs(left_dep - right_dep) <= 1 and left_res and right_res
if not root: return True
return dfs(root)
def maxDepth(self, root):
if not root: return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
6、二叉搜索树
6-1 二叉搜索树的第k大节点
解题思路：考察二叉搜索树特性和二叉树中序遍历
二叉搜索树左中右遍历为小中大，因此把右节点看成左节点，按照中序遍历的变形，进行遍历k次，后直接返回对应值即可
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.right
item = stack.pop()
k -= 1
if k == 0: return item.val
cur = item.left
6-2 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
要求不能创建任何新的节点，只能调整树中节点指针的指向。
解题思路：
先建立一个哨兵节点pre，利用dfs遍历处理，主要处理cur节点。
注意最后要把首尾节点进行连接
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# -- BEGIN --
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
def dfs(cur):
if not cur: return
dfs(cur.left)
# 处理中间cur节点
if self.pre:
self.pre.right = cur
cur.left = self.pre
else:
self.head = cur
self.pre = cur
dfs(cur.right)
if not root: return
self.pre = None
dfs(root)
# 遍历拼接完毕，构建首尾连接，self.pre为最后一个遍历的节点，
self.head.left = self.pre
self.pre.right = self.head
return self.head
# -- END --
# 用于debug使用，输出最终结果
def list2arr(root):
result = []
my_set = set()
cur = root
while cur and cur not in my_set:
my_set.add(cur)
result.append(cur.val)
cur = cur.right
return result
if __name__ == '__main__':
a = Node(4)
b = Node(2)
c = Node(5)
d = Node(1)
e = Node(3)
a.left = b
a.right = c
b.left = d
b.right = e
res = Solution().treeToDoublyList(a)
print(list2arr(res))
6-3 二叉搜索树的后序遍历序列
原题地址：剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同
解题思路：
二叉搜索树的特点是：左子树 < root < 右子树 后序遍历时采用的是：左 右 root , 故可不断对数组进行划分，看左子树和右子树是否符合搜索树顺序。
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(i, j):
if i >= j: return True
cur = i
while postorder[cur] < postorder[j]: cur += 1 # 划分左子树：[i:cur]
left = cur
while postorder[cur] > postorder[j]: cur += 1 # 划分右子树 [left:cur]
# 此时cur应该指向数组中最后一个节点：root
return cur == j and recur(i, left-1) and recur(left, j-1)
return recur(0, len(postorder) - 1)
7、树的子结构
原题地址：剑指 Offer 26. 树的子结构
解题思路：首先构建一个isEqu(cur,target)用来判断当前子树和目标子树是否相同，如果target为null，返回true
然后遍历当前树，当cur.val == b.target时，进行对比，否则分别对比左右子树
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 遍历A树
# 判断是否是子结构
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
"""判断B树是否A树的子结构"""
result = False
if A is not None and B is not None:
if A.val == B.val:
result = self.isEqu(A, B)
if result is False:
result = self.isSubStructure(A.left, B)
if result is False:
result = self.isSubStructure(A.right, B)
return result
# 判断B树是否和A树相同，默认B为null，返回true
def isEqu(self, A: TreeNode, B: TreeNode) -> bool:
if B is None: return True
if A is None: return False
if A.val != B.val: return False
return self.isEqu(A.left, B.left) and self.isEqu(A.right, B.right)
8、二叉树的镜像
原题地址:剑指 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 root is None: return
root.left, root.right = self.mirrorTree(root.right),self.mirrorTree(root.left)
return root
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if root is None: return
q = queue.Queue()
q.put(root)
while not q.empty():
item = q.get()
if item.left: q.put(item.left)
if item.right: q.put(item.right)
# 翻转子节点
item.left, item.right = item.right, item.left
return root
9、对称的二叉树
原题地址：剑指 Offer 28. 对称的二叉树
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def isSymLoop(left, right):
# 都为空，有一个为空，都不为空
if not left and not right: return True
if not left or not right or left.val != right.val: return False
return isSymLoop(left.left, right.right) and isSymLoop(left.right, right.left)
return isSymLoop(root.left, root.right) if root else True
10、二叉树中和为某一值的路径
原文地址：剑指 Offer 34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
题解思路：
二叉树路径遍历的变种，需要在dfs中添加当前路径的sum值
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from typing import List
import copy
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 二叉树路径遍历变种
# 图的遍历：BFS/DFS
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if not root : return []
result = []
def dfs(root, path, ssum):
mypath = copy.deepcopy(path)
if not root.left and not root.right: # 叶子节点，判断路径是否相等
if ssum+root.val == sum:
mypath.append(root.val)
result.append(mypath)
else:
mypath.append(root.val)
ssum += root.val
if root.left: dfs(root.left, mypath, ssum)
if root.right: dfs(root.right, mypath, ssum)
dfs(root, [], 0)
return result
