代碼随想錄DAY16：二叉樹

二叉樹

104. 二叉樹的最大深度

104.二叉樹的最大深度

題目描述

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

思路

遞歸法

疊代法

代碼

遞歸法

/**
 * 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) {
        if(root == NULL)
        {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        int res = max(leftMax,rightMax) + 1;
        return res;
    }
};
           

疊代法（待補充）

111. 二叉樹的最小深度

111.二叉樹的最小深度

題目描述

給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明：葉子節點是指沒有子節點的節點。

思路

遞歸法

疊代法：

每層周遊時，若節點的左右子節點都為NULL，則到達葉子節點，return目前深度。

代碼

/**
 * 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) {
        queue<TreeNode*> que;
        if (root != NULL)   que.push(root);
        int depth = 0;

        while (!que.empty())
        {
            int size = que.size();
            depth ++;
            
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if (node->left)     que.push(node->left);
                if (node->right)    que.push(node->right);
                if (!node->left && !node->right)    return depth;
            }
        }
        return depth;
    }
};
           

完全二叉樹的節點個數

題目描述

給你一棵 完全二叉樹 的根節點 root ，求出該樹的節點個數。

完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2^h 個節點。

思路

1、适用于普通二叉樹的方法

周遊樹中節點，可用遞歸法和疊代法

2、利用完全二叉樹性質

分兩種情況：

（1）滿二叉樹：用 2 ^ 樹深度 - 1，根節點深度為 1

（2）最後一層葉子節點沒有填滿：遞歸左右孩子，直至遞歸到滿二叉樹，回到（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) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL)   que.push(root);
        int res = 0;

        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                res++;
                if (node->left) que.push(node->left);
                if (node->right)    que.push(node->right);
            }
        }
        return res;
    }
};
           

利用完全二叉樹性質處理

//利用完全二叉樹性質處理
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL)   return 0;
        TreeNode* left =root->left;
        TreeNode* right = root->right;
        int leftHeight = 0;
        int rightHeight = 0;
        while (left)
        {
            left = left->left;
            leftHeight++;
        }
        while (right)
        {
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight)
        {
            return (2 << leftHeight) - 1;
        }
        int leftNum = countNodes(root->left);
        int rightNum = countNodes(root->right);
        int sum = leftNum + rightNum + 1;
        return sum;
    }
};