递归和迭代有什么区别？

递归的实质是将问题拆解成一些好处理的子问题，而迭代则是一步一步解决问题

一、递归如何思考？

当我们使用递归的时候，应该思考三件事

1.怎么把大的问题分解成可以处理的小问题

2.拆解到什么程度？

3.怎么归？（临界条件？）

二、迭代如何思考？

迭代的时候，我们应该想的是，根据现有的，我应该怎么做？

以前序遍历为例子

如果使用迭代来做，我应该想的是

前序遍历需要访问根结点，左子树，右子树，当我访问根结点的左子树的时候，根节点这个信息丢失了，导致我没办法再找到右子树

所以我们应当时刻记录根节点，也就是一个顺序表

那么这个顺序表有什么特征呢，最上层的根节点，最先进来，但是只有我们把他的左子树那边全部遍历完，才轮到它的右子树，所以他是最后进来的，所以这就是一个栈结构，先进后出

而栈顶恰恰是当前访问节点的根节点

创建一个栈，先左行，记录根节点，

然后直到左子树为空，这时候访问此时栈顶的右结点，

那此时这个栈顶元素是否利用完了？没错，因为保留这个栈顶元素就是为了访问右子树，所以可以出栈了

那么到这个右子树之后呢，还是要左行，然后和上面是一样的

什么时候结束呢，当这个栈为空的时候结束！也就是所有根节点的右子树都已经访问完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> path;
        stack<TreeNode*> s;
        if(!root) return path;
        s.push(root);
        path.push_back(root->val);
        while(!s.empty())
        {
            if(root && root->left) 
            {
                root = root->left;
                s.push(root);
                path.push_back(root->val);
            }
            else{
                root = s.top()->right;
                s.pop();
                if(root) 
                {
                    s.push(root);
                    path.push_back(root->val);
                }
            }
        }
        return path;
    }