【LeetCode 31】104.二叉樹的最大深度

文章目錄

• ​​【LeetCode 31】104.二叉樹的最大深度​​
• ​​一、題意​​
• ​​二、思考過程​​

• ​​2.1遞歸法：​​

一、題意

二、思考過程

**思路：**二叉樹的最大深度就是根節點的高度。

方法：求根節點的高度就是求後序周遊即可。

2.1遞歸法：

• 确定遞歸函數的參數和傳回值

int getDepth(TreeNode * node)      

• 确定終止條件

if(node==NULL) return 0;      

• 确定單層遞歸邏輯

确定單層遞歸的邏輯：先求它的左子樹的深度，再求的右子樹的深度，最後取左右深度最大的數值 再+1 （加1是因為算上目前中間節點）就是目前節點為根節點的樹的深度。

int leftDepth=getDepth(node->left);//左
        int rightDepth=getDepth(node->right);//右
        int depth=1+max(leftDepth,rightDepth);//中      

class Solution {
public:
    int getDepth(TreeNode* node)
    {
        if(node==NULL) return 0;

        int leftDepth=getDepth(node->left);//左
        int rightDepth=getDepth(node->right);//右
        int depth=1+max(leftDepth,rightDepth);//中
        return depth;
    }

    int maxDepth(TreeNode* root)
    {
        return getDepth(root);
    }
};