目 录CONTENT

文章目录

二叉树 | 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 | 222.完全二叉树的节点个数

RobKing
2023-09-21 / 0 评论 / 1 点赞 / 246 阅读 / 947 字

二叉树 | 104.二叉树的最大深度 559.n叉树的最大深度

111.二叉树的最小深度 | 222.完全二叉树的节点个数

104. 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return left + 1
    }
    return right + 1
}

C++实现

/**
 * 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 maxDepth(TreeNode* root) {
        // 到根节点,高度为0
        if(root == nullptr) return 0;
        // 左右中 后序遍历
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        int res = 1 + max(left, right);
        return res;
    }
};
  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)

  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)

    而根节点的高度就是二叉树的最大深度

559. N 叉树的最大深度

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    res := 0
    for i := 0; i < len(root.Children); i ++ {
        tmp := maxDepth(root.Children[i])
        res = max(res, tmp)
    }
    return res + 1
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}
/*
// 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) {
        if(root == nullptr) return 0;
        int size = root->children.size();
        int maxv = 0;
        for(int i = 0; i < size; i ++ ) {
            // 左右子树中 的最大值
            maxv = max(maxv, maxDepth(root->children[i]));
        }
        // 包括自己 +1
        return maxv + 1;
    }
};

非递归

class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        queue<Node *> qu;
        int res = 0;
        qu.push(root);
        while(!qu.empty()) {
            res ++;
            int size = qu.size();
            while(size --) {
                auto top = qu.front();
                qu.pop();
                for(int i = 0; i < top->children.size(); i ++ ) {
                    if(top->children[i]) qu.push(top->children[i]);
                }
            }
        }
        return res;
    }
};

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    // 思路:递归计算左边和右边,返回左边加右边再加自己
    if root == nil {
        return 0
    }
    left := countNodes(root.Left)
    right := countNodes(root.Right)
    return left + right + 1
}

C++实现

/**
 * 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 countNodes(TreeNode* root) {
        // 左右子树所有节点数之和
        if(root == nullptr) return 0;
        int left = countNodes(root->left);
        int right = countNodes(root->right);
        int res = left + right;
        // 还要加上自身
        return res + 1;
    }
};

总结

  • 今天的几道题还是很容易的,不到20分钟二刷就秒了
  • 深度就是 左边和右边的最大深度+1;节点数就是左边的节点数+右边的结点数+1
1

评论区