leetcode算法总结 —— DFS深度优先搜索

DFS

模板

dfs(TreeNode* root, int path) { //父节点要传给子节点值，则放到递归的形参中。`void dfs(TreeNode* root, int path)`    if(root == nullptr) return;    //return放递归上面则会终止到当前节点，不继续向下面子树遍历，不执行后面的语句    //前序遍历自顶向下，按照根左右的顺序遍历    int leftV = dfs(root->left); //是左子树向当前节点返回的值，这个返回值的定义具体要看当前函数的return是什么    int rightV = dfs(root->right);    //后序遍历：自底向上，按照左右根的顺序    return xxx; //当前节点返回给父节点的值，放在return中。}

解读：

  • root->left = xxx 才是指向，root = root->left是移动指针遍历

  • 父节点要传给子节点值，则放到递归的形参中。void dfs(TreeNode* root, int path)

  • 在左右递归上面写的语句是前序遍历，也就是我们要自顶向下执行顺序来执行该语句。在左右递归下面的语句属于后序遍历，自底向上遍历处理。这个遍历顺序是根左右就需要看我们dfs(root->left)和dfs(root->right)的顺序也可以根右左，dfs(root->right)在dfs(root->left)前面

  • return放递归上面则会终止到当前节点，不继续向下面子树遍历，不执行后面的语句，但还是会回溯，也就是回到父节点。

  • int a = dfs(root->left) 是左子树向当前节点返回的值，这个返回值的定义具体要看当前函数的return是什么

  • 当前节点返回给父节点的值，放在return中

自顶向下（根节点到叶子节点）（前序处理）（向下传参）

递归条件中放参数作为父节点传给当前节点的值

    1. 翻转二叉树

    1. 求根到叶子节点数字之和（好理解）

    1. 路径总和

    1. 左叶子之和

    1. 二叉树的所有路径

    1. 路径总和II(两种解法)(加深理解)（对比257）

同时遍历两个树

    1. 相同的树

    1. 对称二叉树

自底向上（子节点到子节点） (后序处理)

    1. 平衡二叉树

    1. 寻找重复的子树（打印查看遍历顺序）

    1. 二叉树的直径

    1. 二叉树中的最大路径和

    1. 二叉树展开为链表（右左根的顺序）

    1. 二叉树的最近公共祖先

    1. 完全二叉树的节点个数

构建二叉树

构建二叉树模板

通过前/后 和中序遍历构造二叉树

TreeNode *dfs(vector<int> &preorder, int start, int end) {        if(start > end) {            return nullptr;        }        //每次遍历的节点顺序要确定.遍历数组        rootValue = nums[i];        //然后看用什么顺序创建二叉树：一种是：根->创建左子树->创建右子树的顺序来创建二叉树        //前序遍历创建节点        TreeNode *root = new TreeNode(rootValue);        //因为是创建二叉树，需要让左右子树指针去指        root->left = dfs(preorder, start, midIndex-1); //递归左子树为左子树的所有元素        root->right = dfs(preorder, midIndex 1, end);   //递归右子树的所有元素放入右子树        return root;    }

注意构建顺序要和遍历数组顺序相同

    1. 从前序与中序遍历序列构造二叉树

    1. 从中序与后序遍历序列构造二叉树

    1. 将有序数组转换为二叉搜索树

    1. 有序链表转换二叉搜索树

    1. 合并二叉树

来源：https://www.icode9.com/content-1-845101.html

赞 (0)

相关推荐