DFS和BFS+栈和队列

问题

给定一个二叉树，找出其最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

解

这个问题用递归的深度优先搜索可以很快完成
但为了实践DFS的非递归写法和BFS算法，再重新实现一遍

递归法

思路

实现函数maxDepth，计算输入节点的最大深度。
具体到某个节点时，分为这个节点为NULL或者非NULL两种情况

1. 为非NULL时，说明这个节点存在，因此高度为1 + 左右子树中最高的那个树的高度，左右子树中最高的那个树的高度就通过递归进行计算。
2. 为NULL时，即这个节点根本不存在了，因此直接返回高度0.这实际上也是第一种情况的递归终点，即递归到叶子节点返回。

   1
   2
   3
   4
   5
   6
   7
   8
   9
   int maxDepth(TreeNode* root) {
    if(root == NULL) return 0;
    int l = 0, r = 0;
    if(root->left != NULL)
        l = maxDepth(root->left);
    if(root->right != NULL)
        r = maxDepth(root->right);
    return max(l, r) + 1; 
   }
   

DFS非递归

思路

DFS的非递归实现实际上是完成计算机自动为我们完成的栈操作，因为程序自己开的栈和我们运行时开的栈在计算机中实际存放的位置不同，因此可以开的最大栈不同，可以避免栈溢出的问题。

1. 对节点不存在的情况，即root == NULL的情况，直接返回0，此处时处理边界情况
2. 对节点存在的情况，使用STL的stack申请一个栈，根据DFS的定义
   • 首先一路向左，遍历到最左边的叶子节点p
   • 虽然此时p已无左右子树，但是因为中间其他节点回溯的时候也需要处理，因此先以节点p为根，将p从栈中弹出，然后遍历它的右子树（对p来说实际上并没有做什么），右子树继续按DFS进行遍历，直到遍历结束

int maxDepth_stack(TreeNode* root) {
    if(root == NULL) return 0;
    int deep = 0, maxdeep = 0;
    TreeNode* p;
    p = root;
    stack<pair<TreeNode*, int>> s;
    while(!s.empty() || p){
        // 如果当前节点不为NULL，则将其压入栈中，深度+1
        while(p){
            s.push(pair<TreeNode*, int>(p, ++deep));
            p = p->left;  // 继续向左遍历，直到叶子节点
        }
        p = s.top().first;  // 因为上一步p被继续赋予了左子树，而实际上并不存在，其值为NULL，
                            // 实际上的叶子节点是栈顶元素，因此需要对p重新赋值
        deep = s.top().second;
        if(maxdeep < deep) maxdeep = deep;
        s.pop();  // 接下来开始遍历p的右子树，p已经没用了，将p弹出
        p = p->right;
    }
    return maxdeep;
}

BFS

思路

BFS本来就不是递归实现，通常BFS使用队列进行实现

先声明一个队列，然后每一次新开一层地时候，保存上一层节点的数量，根据从左到右的顺序，对上一层的每个节点的左右子节点访问，即从队头取出一个元素，弹出已经访问过左右子节点的节点，并将其左右子节点依次放入队列尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxDepth(TreeNode* root) {
    if(root == NULL) return 0;
    int deep = 0;
    TreeNode* p;
    p = root;
    queue<TreeNode*> q;
    q.push(p);
    while(!q.empty()){
        int n = q.size();  // 维护上一层的节点数量
        deep++;
        for(int i = 0; i < n; i++){
            p = q.front();  // 取出队头，依次访问上一层的每个节点
            q.pop();  // 已经访问过，故弹出
            if(p->left) q.push(p->left);  // 将其左右子节点依次放入队列尾部
            if(p->right) q.push(p->right);
        }
    }
    return deep;
}

C++中的栈和队列

stack

stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要 的，在不指定容器类型时，默认的容器类型为deque

定义stack对象的示例代码：

1
2
stack<int> s1;
stack<string> s2;

stack 的基本操作：

1
2
3
4
5
s.push(x);  // 入栈
s.pop();  // 出栈,出栈操作只是删除栈顶元素，并不返回该元素
s.top();  // 访问栈顶,返回该元素
s.empty();  // 判断栈空，当栈空时，返回true
s.size();  // 获取栈中的元素个数

queue

queue 模板类的定义在<queue>头文件中
与stack模板类很相似，queue模板类也需要两个模板参数，一个是元素类型，一个容器类 型，只有元素类型是必要的，容器类型是可选的，默认为deque类型

定义queue对象的示例代码：

1
2
queue<int> q1;
queue<double> q2;

queue的基本操作：

1
2
3
4
5
6
q.push(x);  // 入队,将x 接到队列的末端
q.pop();  // 出队弹出队列的第一个元素，注意，不会返回被弹出元素的值
q.front();  // 访问队首元素，即最早被压入队列的元素
q.back();  // 访问队尾元素，即最后被压入队列的元素
q.empty();  // 判断队列空，当队列空时，返回true
q.size();  // 队列中的元素个数

• Previous
  高级人工智能笔记-知识1
• Next
  C++中的vector、queue、deque、priority_queue