深搜(DFS)&广搜(BFS)

基本概念

深度优先搜索：Depth First Search, DFS
广度优先搜索：Breadth First Search, BFS
路径搜索的两个基本思路，一个以深度优先（一条路走到黑），另一个以广度优先（每个分岔口都走一下看看）
主要可以参考二叉树的遍历：

• 前序遍历、中序遍历、后序遍历属于深度优先搜索DFS
• 层次遍历属于广度优先搜索BFS

104. 二叉树的最大深度

方法一：递归

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
        {
            return 0;
        }
        else
        {
            int left_height = maxDepth(root->left);
            int right_height = maxDepth(root->right);
            return max(left_height,right_height)+1;
        }
    }
};

方法二：迭代

我们还可以在栈的帮助下将上面的递归转换为迭代。
我们的想法是使用 DFS 策略访问每个结点，同时在每次访问时更新最大深度。
所以我们从包含根结点且相应深度为 1 的栈开始。然后我们继续迭代：将当前结点弹出栈并推入子结点。每一步都会更新深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*>q;//队列， q是队列对象
        if(root!=nullptr){//用nullptr 不用NULL， 这样不会出现构造函数int 空，精确为空指针
            q.push(root); //此时q队列 size为1，只有根节点
        }
        int depth = 0; //初始depth
        while(q.size()!=0){ //遍历我们的队列
            int n = q.size(); // n等于 队列里面元素的个数
            for(int i=0; i<n; i++){ // 把队列里面每个元素都进行处理
                TreeNode* tr = q.front(); //把队列第一个元素赋值给tr
                q.pop(); //把队列第一个元素弹出， 先进先出原则
                if(tr->left!=nullptr){ //如果该元素有左子结点，则把左子结点推入队列q
                    q.push(tr->left);
                }
                if(tr->right!=nullptr){//如果有右子结点，则把右子结点推入队列，
                    q.push(tr->right);
                }   //for循环会把本层树的所有结点都作为root遍历他们各自的左右子，然后把该层结点都弹出（在if之前弹出， 弹出前把该元素赋值给tr，每次tr都会更新）
            }
            depth++;//一层处理完，depth++， 深度+1 ， 非常好理解
        }//直到都没有左右子结点， q则没有push元素进来了，则跳出，返回depth
        return depth;
    }
};

144. 二叉树的前序遍历(mdium)

方法一：递归

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root,result);
        return result;
    }
    void preorder(TreeNode* root, vector<int> &result)
    {
        if(root)
        {
            result.push_back(root->val);
            preorder(root->left,result);
            preorder(root->right,result);
        }
    }
};

方法二：迭代

    vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    stack.push(root);
    while(!stack.empty()){
        // 取出栈顶
        root = stack.top();
        stack.pop();
        // 右结点先入栈（后访问）
        if(root->right != NULL)
            stack.push(root->right);
        // 左节点后入栈（先访问）
        if(root->left != NULL)
            stack.push(root->left);
        // 访问
        res.push_back(root->val);
    }
    return res;

94. 二叉树的中序遍历(mdium)

方法一：递归

void inorder(TreeNode* root, vector<int> &result){
    if(root != NULL){
        inorder(root->left, result);
        result.push_back(root->val);   // !!!
        inorder(root->right, result);
    }
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorder(root, result);
    return result;
}

方法二：迭代

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    do{
        // 找到以root为根的子树的最左节点
        while(root != NULL){
            stack.push(root);
            root = root->left;
        }
        // 以root为根的子树的最左节点如果存在
        if(!stack.empty()){
            // 弹出栈顶
            root = stack.top();
            stack.pop();
            // 访问
            res.push_back(root->val);
            // 进入右结点
            root = root->right;
        }
    }while(root != NULL || !stack.empty());
    // 返回结果
    return res;
}

145. 二叉树的后序遍历(hard)

左->右->中——这个访问顺序不易实现，需要记录已访问的节点
反序遍历（中->右->左）+翻转结果是一种作弊解法，并不是真正意义上的后序遍历
https://leetcode-cn.com/problems/binary-tree-postorder-traversal
可以与前序遍历比较一下——

1. 每次循环取出栈顶的时候不直接出栈，只有左右节点都访问过了才能出栈
2. 如果左/右节点未访问过，才会进入对应分支
3. 只有左右节点都访问过了或者不存在，才能访问当前节点

   方法一：递归

   class Solution {
   public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postorder(root,result);
        return result;
    }
    void postorder(TreeNode* root, vector<int>& result)
    {
        if(root!=NULL)
        {
            postorder(root->left,result);
            postorder(root->right,result);
            result.push_back(root->val);
        }
    }
   };

   方法二：迭代

   // 可以根前序遍历比较一下
   vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    unordered_set<TreeNode*> visited;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    stack.push(root);
    while(!stack.empty()){
        bool left_visited = true, right_visited = true;
        // 取出栈顶（但不弹出）
        root = stack.top();
        // 如果右结点未访问，则入栈（先入栈后访问）
        if(root->right != NULL && visited.find(root->right) == visited.end()){
            right_visited = false;
            stack.push(root->right);
        }
        // 如果左节点未访问，则入栈（后入栈先访问）
        if(root->left != NULL && visited.find(root->left) == visited.end()){
            left_visited = false;
            stack.push(root->left);
        }
        // 如果左右节点都访问过了，那么可以访问本节点
        if(left_visited && right_visited){
            visited.insert(root);
            res.push_back(root->val);
            stack.pop();
        }
    }
    return res;
   }

   102. 二叉树的层序遍历

   方法一：宽度优先搜索

• 首先根元素入队

• 当队列不为空的时候

  • 求当前队列的长度 si_s__i

  • 依次从队列中取 si_s__i 个元素进行拓展，然后进入下一次迭代

    class Solution {
    public:
    vector<vector<int>> levelOrder(TreeNode* root) {
       vector <vector <int>> ret;
       if (!root) return ret;
       queue <TreeNode*> q;
       q.push(root);
       while (!q.empty()) {
           int currentLevelSize = q.size();
           ret.push_back(vector <int> ());
           for (int i = 1; i <= currentLevelSize; ++i) {
               auto node = q.front(); q.pop();
               ret.back().push_back(node->val);
               if (node->left) q.push(node->left);
               if (node->right) q.push(node->right);
           }
       }
       return ret;
    }
    };