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中。 } 解读:
自顶向下(根节点到叶子节点)(前序处理)(向下传参)递归条件中放参数作为父节点传给当前节点的值
同时遍历两个树
自底向上(子节点到子节点) (后序处理)
构建二叉树构建二叉树模板 通过前/后 和中序遍历构造二叉树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; } 注意构建顺序要和遍历数组顺序相同
|
|