Day 2 面试算法练习：二叉树遍历(前序，中序，后序)

核心思路：根左右，左根右，左右根。递归时每一层都是一个新盒子，最后将它们合在一起，

res += 相当于 res.extend

时间复杂度：o(n)

class TreeNode: def __init__(self, v): self.value = v self.left = None self.right = None def post_order(node): if node is None: return [] l_res = post_order(node.left) r_res = post_order(node.right) res = [node.value] return res + l_res + r_res def pre_order(node): if node is None: return print(node.value) pre_order(node.left) pre_order(node.right) def in_order(node): res = [] if node is None: return res res += in_order(node.left) res.append(node.value) res += in_order(node.right) return res if __name__ == '__main__': t = TreeNode(1) t.left = TreeNode(2) t.right = TreeNode(3) t.left.left = TreeNode(4) t.right.left = TreeNode(5) print(post_order(t))