树——二叉树的深度¶

树的深度¶

由此可以衍生出最大深度和最小深度。

二叉树最大深度¶

LeetCode 104 二叉树的最大深度

递归解法：

/**
 * 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        return 1 + max(maxDepth(root -> left), maxDepth(root -> right));
    }
};

迭代解法，相当于层序遍历

/**
 * 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        int level = 0;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            ++level;
            for (int i = 0; i < n; ++i) {
                TreeNode *tmp = q.front(); q.pop();
                if (tmp -> left) q.push(tmp -> left);
                if (tmp -> right) q.push(tmp -> right);
            }
        }

        return level;
    }
};

二叉树最小深度¶

LeetCode 111 二叉树的最小深度

递归解法：

/**
 * 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 minDepth(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        if (!root -> left && !root -> right) return 1;

        int l = INT_MAX - 1, r = INT_MAX - 1;
        if (root -> left) l = minDepth(root -> left);
        if (root -> right) r = minDepth(root -> right);

        return 1 + min(l, r);
    }
};

迭代解法，仍然是层序遍历的思路，当一个节点的左右节点都为空的时候，表明此节点是叶节点，直接返回即可。

/**
 * 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 minDepth(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        queue<TreeNode *> q;
        q.push(root);
        int level = 0;
        while (!q.empty()) {
            int n = q.size();
            ++level;
            for (int i = 0; i < n; ++i) {
                TreeNode *tmp = q.front(); q.pop();
                if (!tmp -> left && !tmp -> right) return level;
                if (tmp -> left) q.push(tmp -> left);
                if (tmp -> right) q.push(tmp -> right);
            }
        }

        return level;
    }
};

N叉树的最大深度¶

递归解法：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        auto &v = root -> children;
        int res = 0;
        for (auto e : v) {
            res = max(res, maxDepth(e));
        }

        return 1 + res;
    }
};

迭代解法：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return 0;
        queue<Node *> q;
        q.push(root);
        int level = 0;
        while (!q.empty()) {
            int n = q.size();
            ++level;
            for (int i = 0; i < n; ++i) {
                Node *tmp = q.front(); q.pop();
                auto &v = tmp -> children;
                for (auto e : v) q.push(e);
            }
        }

        return level;
    }
};

特定深度节点链表¶

面试题 04.03. 特定深度节点链表

层序遍历的变形。

面试题 55-1 二叉树的深度
LeetCode 104 二叉树的最大深度
LeetCode 111 二叉树的最小深度
LeetCode 559 N叉树的最大深度
面试题 04.03. 特定深度节点链表