专项训练——深度优先搜索

文章目录

• 1. 二叉树的深度
• 2. 二叉树的最小深度
• 3. 路径总和
• 4 翻转二叉树
• 5. 相同的树
• 6. 对称二叉树
• 7. 从根节点到叶节点的路径数字之和
• 8. 二叉树的最近公共祖先

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) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

广度优先遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 使用STL版本：
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty())
        {
            int sz = Q.size();
            while (sz > 0)
            {
                TreeNode* node = Q.front(); Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans ++ ;
        }
        return ans;
    }
};

// 未使用STL版本（考试版本）：
const int N = 10010;
TreeNode* q[N];

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        memset(q, NULL, sizeof q);
        int hh = 0, tt = -1;
        q[ ++ tt] = root;
        int ans = 0;
        while (hh <= tt)
        {
            int sz = tt - hh + 1;
            while (sz > 0)
            {
                TreeNode* node = q[hh ++ ];
                if (node->left) q[ ++ tt] = node->left;
                if (node->right) q[ ++ tt] = node->right;
                sz -- ;
            }
            ans ++ ;
        }
        return ans;
    }
};

2. 二叉树的最小深度

题目链接

深度优先搜索：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return 1;

        int min_depth = 2e9;
        if (root->left != nullptr)
            min_depth = min(minDepth(root->left), min_depth);
        if (root->right != nullptr)
            min_depth = min(minDepth(root->right), min_depth);

        return min_depth + 1;
    }
};

广度优先搜索：注意维护每一个结点的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

// 考试版本：
const int N = 100010;
TreeNode* q[N];
int depth[N]; // 记录每个结点的深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        
        memset(q, NULL, sizeof q);
        int hh = 0, tt = -1;

        q[ ++ tt] = root;
        depth[tt] = 1;
        
        while (hh <= tt)
        {
            TreeNode * node = q[hh];
            if (node->left == nullptr && node->right == nullptr)
                return depth[hh];
 
            if (node->left != nullptr) q[ ++ tt] = node->left, depth[tt] = depth[hh] + 1;
            if (node->right != nullptr) q[ ++ tt] = node->right, depth[tt] = depth[hh] + 1;
            hh ++ ;
        }
        return 0;
    }
};

// STL版本：
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        queue<pair<TreeNode*, int>> que;
        que.emplace(root, 1);
        while (!que.empty())
        {
            TreeNode* node = que.front().first; 
            int depth = que.front().second;
            que.pop();

            if (node->left == nullptr && node->right == nullptr)
                return depth;
            
            if (node->left != nullptr)
                que.emplace(node->left, depth + 1);
            if (node->right != nullptr)
                que.emplace(node->right, depth + 1);
        }
        return 0;
    }
};

3. 路径总和

题目链接

广度优先搜索：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        
        queue<TreeNode *> que_node; // 记录结点
        queue<int> que_val; // 记录从根节点到该结点的值之和
        que_node.push(root);
        que_val.push(root->val);

        while (!que_node.empty())
        {
            TreeNode* now = que_node.front(); que_node.pop();
            int temp = que_val.front(); que_val.pop();

            if (now->left == nullptr && now->right == nullptr)
            {
                if (temp == targetSum)
                    return true;
                continue;
            }
            
            if (now->left != nullptr)
            {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }

            if (now->right != nullptr)
            {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }

        return false;
    }
};

深度优先遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr)
            return false;
        
        if (root->left == nullptr && root->right == nullptr)
            return targetSum == root->val;
        
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

4 翻转二叉树

题目链接

递归：自底向上

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return nullptr;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

BFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        queue<TreeNode*> q;
        q.push(root);
        while (q.size())
        {
            TreeNode* node = q.front(); q.pop();
            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        return root;
    }
};

DFS：自顶向下（栈里面仅保存当前结点的两个儿子）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        stack<TreeNode*> st;
        st.push(root);
        while (st.size())
        {
            int sz = st.size();
            for (int i = 0; i < sz; i ++ )
            {
                TreeNode* cur = st.top(); st.pop();
                TreeNode* tmp = cur->left;
                cur->left = cur->right;
                cur->right = tmp;
                if (cur->left != nullptr) st.push(cur->left);
                if (cur->right != nullptr) st.push(cur->right);
            }
        }
        return root;
    }
};

5. 相同的树

题目链接

DFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        else if (p == nullptr || q == nullptr) return false;
        else if (p->val != q->val) return false;
        else return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

BFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr)
            return true;
        else if (p == nullptr || q == nullptr)
            return false;
            
        queue<TreeNode*> tmpQ;
        tmpQ.push(p); tmpQ.push(q);
        while (tmpQ.size())
        {
            p = tmpQ.front(); tmpQ.pop();
            q = tmpQ.front(); tmpQ.pop();

            if (p == nullptr && q == nullptr)
                continue;
            if ((p == nullptr || q == nullptr) || p->val != q->val)
                return false;
            
            tmpQ.push(p->left);
            tmpQ.push(q->left);
            tmpQ.push(p->right);
            tmpQ.push(q->right);
        }

        return true;
    }
};

6. 对称二叉树

题目链接

DFS：

/**
 * 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:
    bool check(TreeNode* p, TreeNode *q)
    {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

BFS：

/**
 * 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:
    bool check(TreeNode* u, TreeNode* v)
    {
        queue<TreeNode*> q;
        q.push(u); q.push(v);
        while (q.size())
        {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || u->val != v->val) return false;

            q.push(u->left); q.push(v->right);
            q.push(u->right); q.push(v->left);
        }
        
        return true;
    }

    bool isSymmetric(TreeNode* root) 
    {
        return check(root, root);
    }
};

7. 从根节点到叶节点的路径数字之和

题目链接

DFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root, int prevSum)
    {
        if (root == nullptr) return 0;

        int sum = prevSum * 10 + root->val;

        if (root->left == nullptr && root->right == nullptr) return sum;
        else return dfs(root->left, sum) + dfs(root->right, sum);
    }

    int sumNumbers(TreeNode* root) 
    {
        return dfs(root, 0);
    }
};

BFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (root == nullptr) return 0;
        int sum = 0;
        queue<TreeNode*> nodeQ; queue<int> numQ;
        nodeQ.push(root); numQ.push(root->val);
        while (nodeQ.size())
        {
            TreeNode* node = nodeQ.front(); nodeQ.pop();
            int num = numQ.front(); numQ.pop();

            TreeNode* left = node->left, *right = node->right;
            if (left == nullptr && right == nullptr) sum += num;
            else 
            {
                if (left != nullptr)
                {
                    nodeQ.push(left);
                    numQ.push(num * 10 + left->val);
                }
                if (right != nullptr)
                {
                    nodeQ.push(right);
                    numQ.push(num * 10 + right->val);
                }
            }
        }

        return sum;
    }
};

8. 二叉树的最近公共祖先

题目链接

DFS：

/**
 * 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:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson)))
            ans = root;
        return lson || rson || (root->val == p->val || root->val == q->val);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

BFS：

/**
 * 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:
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> vis;

    void dfs(TreeNode* root)
    {
        if (root->left != nullptr)
        {
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr)
        {
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = nullptr;
        dfs(root);
        while (p != nullptr)
        {
            vis[p->val] = true;
            p = fa[p->val];
        }

        while (q != nullptr)
        {
            if (vis[q->val]) return q;
            q = fa[q->val];
        }
        return nullptr;
    }
};