1. void traverse(TreeNode root) {
    2.     for (TreeNode child : root.childern)
    3.         // 前序遍历需要的操作
    4.         traverse(child);
    5.         // 后序遍历需要的操作
    6. }

    image.png
    image.png

    1. for 选择 in 选择列表:
    2.     # 做选择
    3.     将该选择从选择列表移除
    4.     路径.add(选择)
    5.     backtrack(路径, 选择列表)
    6.     # 撤销选择
    7.     路径.remove(选择)
    8.     将该选择再加⼊选择列表

    image.png

    不管怎么优化，都符合回溯框架，而且时间复杂度都不 可能低于 回溯算法 - 图4。因为穷举整棵决策树是无法避免的。这也是回溯算法的⼀ 个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷 举，复杂度⼀般都很高。

    N 皇后问题