跳到主要内容

树遍历模板

· 阅读需 1 分钟

二叉树遍历​

void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

N 叉树遍历​

void traverse(ListNode root) {
    for(child of root.children){
        // 前序遍历代码
    traverse(child);
    // 后序遍历代码
    }
}

二叉搜索树遍历​

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target)
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

链表遍历​

这里链表遍历得着重说明一下，为什么将它放到树的遍历模板中呢？因为链表可以看作是一颗每个节点都只有一个子节点的树，因此也可以用树遍历的思想遍历链表

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}