泪眼朦胧

V1

2022/02/07阅读:83主题:默认主题

递归怎么才能写对?

每次写递归都是碰运气写对,递归到底怎么写?

递归看似简单好理解,但是经常一写就错。

编写递归代码时,掌握这三部分,可以保证大家写出正确的递归算法。

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归过程中需要处理的,需要处理的加在递归函数的参数上,并且还要确认递归函数的返回值以确认返回值的类型。
  2. 递归的终止条件: 避免忘记写递归函数的终止条件或者写错导致内存栈溢出。
  3. 单次递归需要完成的工作:确定单次递归需要做的事件,多层递归就把整件事情解决了。

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

这里以二叉树的前中后序遍历来尝试一下。

二叉树的前序遍历, 先遍历根节点,再遍历左子树节点,再遍历右子树节点。

  1. 确定递归函数的参数和返回值: 递归过程需要对一个vector 进行追加操作,追加节点的值,也就是前序遍历的结果,vector需要作为递归函数的参数,遍历的结果直接放进了vector,不需要返回值,所以递归函数返回值为void。

        void Traversal(TreeNode *node, vector<int> &ans) {
        }
  2. 递归函数的终止条件: 当遍历节点为空时,递归结束了。

        void Traversal(TreeNode *node, vector<int> &ans) {
            if (node == nullptr) {
                return;
            }
        }
  3. 单层递归需要做的事: 前序遍历,中左右,所以单层递归时,先加入根节点的值,再递归左子节点,再递归右子节点。

        void Traversal(TreeNode *node, vector<int> &ans) {
            if (node == nullptr) {
                return;
            }
            ans.push_back(root->val);  // 先根
            Traversal(node->left);  // 左
            Traversal(node->right);  // 右
        }

完整的代码像这样:

class Solution {
public:
    vector<intpreorderTraversal(TreeNode* root) {
        vector<int> ans;
        Traversal(root, ans);
        return ans;
    }

private:
    void Traversal(TreeNode *root, vector<int> &ans) {
        if (root == nullptr) {
            return;
        }
        ans.push_back(root->val);  // 先根
        Traversal(root->left, ans);  // 左
        Traversal(root->right, ans);  // 右
    }
}

中序遍历,后序遍历也是同样的道理,快去试试吧。

分类:

后端

标签:

后端

作者介绍

泪眼朦胧
V1