以下題解的更詳細(xì)思路來(lái)自于:代碼隨想錄 (programmercarl.com)

前言

二叉樹(shù)的高度與深度

這里先補(bǔ)充一下二叉樹(shù)深度和高度的概念

高度:二叉樹(shù)中任意一個(gè)節(jié)點(diǎn)到葉子結(jié)點(diǎn)的距離

深度:二叉樹(shù)中任意一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離

下面給出一個(gè)圖便于理解

獲取高度與深度的遍歷方式

高度:后序遍歷

深度:前序遍歷

那么為什么是這兩種方式呢?

高度:(從下往上計(jì)數(shù))后序遍歷可以獲取左右子樹(shù)的高度最后返回給父節(jié)點(diǎn)

深度:(從上往下計(jì)數(shù))往下遍歷一個(gè)我們就加1,也符合求深度的過(guò)程,前序遍歷剛好可以滿(mǎn)足需求

?LeetCode T104 二叉樹(shù)的最大深度

題目鏈接:104. 二叉樹(shù)的最大深度 - 力扣（LeetCode）

題目思路:

首先我要說(shuō)的是,這道題雖然是求最大深度,但是前序遍歷和后序遍歷都可以解決問(wèn)題,這里我們選擇使用后序遍歷解決問(wèn)題,有人會(huì)問(wèn),剛剛不是說(shuō)前序遍歷更好解決深度問(wèn)題嗎,為什么使用后序遍歷呢?這是因?yàn)?span style="color:#fe2c24;">最大深度就是二叉樹(shù)的根節(jié)點(diǎn)的高度,?這里我們將最大深度轉(zhuǎn)化為了根節(jié)點(diǎn) 的高度來(lái)求解,我們?nèi)匀徊捎眠f歸去求解,分三步.

1.確定返回值和參數(shù)類(lèi)型

int getHeight(TreeNode node)

2.確定遞歸結(jié)束條件

if(node == null)
    {
        return 0;
    }

3.確定單層遞歸的代碼

        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        int height = leftHeight>rightHeight?leftHeight+1:rightHeight+1;
        return height;

題目代碼:

class Solution {
    public int maxDepth(TreeNode root) {
        return getHeight(root);

    }
    public int getHeight(TreeNode node)
    {
        if(node == null)
        {
            return 0;
        }
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        int height = leftHeight>rightHeight?leftHeight+1:rightHeight+1;
        return height;
    }
}

LeetCode T111 二叉樹(shù)的最小深度

題目鏈接:111. 二叉樹(shù)的最小深度 - 力扣（LeetCode）

題目思路:

這題我們也能延續(xù)上題的思想,不過(guò)需要做特殊的處理,我們這里同樣使用后序遍歷來(lái)解決問(wèn)題,但是要注意不是在上題的基礎(chǔ)上把最大值改成最小值即可,因?yàn)檫@里我們是從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的距離,這里假設(shè)我們左子樹(shù)為空,用上題的求最大深度的思路解決問(wèn)題就會(huì)發(fā)現(xiàn)不成立,如果依據(jù)上題的思路這里的最小深度就為1,而實(shí)際上這題的最小深度是3,這里我們開(kāi)始遞歸三部曲

1.確定參數(shù)和返回值

 public int getHeight(TreeNode node)

2.確定遞歸結(jié)束條件

if(node == null)
    {
        return 0;
    }

3.確定單層遞歸邏輯

        int rightHeight = getHeight(node.right);
        int leftHeight = getHeight(node.left);
        if(node.left == null && node.right != null)
        {
            return rightHeight+1;
        }
        if(node.left != null && node.right == null)
        {
            return leftHeight+1;
        }
        return leftHeight>rightHeight?rightHeight+1:leftHeight+1;

這里我們要考慮某個(gè)子樹(shù)為空而另一個(gè)子樹(shù)不為空的情況,我們?nèi)シ祷夭粸榭盏淖訕?shù)+1

題目代碼:

class Solution {
    public int minDepth(TreeNode root) {
        return getHeight(root);

    }
    public int getHeight(TreeNode node)
    {
        if(node == null)
        {
            return 0;
        }
        int rightHeight = getHeight(node.right);
        int leftHeight = getHeight(node.left);
        if(node.left == null && node.right != null)
        {
            return rightHeight+1;
        }
        if(node.left != null && node.right == null)
        {
            return leftHeight+1;
        }
        return leftHeight>rightHeight?rightHeight+1:leftHeight+1;
    }
}

LeetCode T222 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

題目鏈接:力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

題目思路:

這里我們知道對(duì)于滿(mǎn)二叉樹(shù),我們的節(jié)點(diǎn)數(shù)是2^(深度-1)次方,由此我們可以判斷如果左邊遞歸到底的深度等于右邊遞歸到底的深度,那么就可以使用這個(gè)公式計(jì)算,這樣也減少了對(duì)中間節(jié)點(diǎn)的遍歷.我們繼續(xù)進(jìn)行遞歸三部曲(后序遍歷)

1.返回值和形參列表

public int getNum(TreeNode node)

2.終止條件

        if(node == null)
        {
            return 0;
        }
        int leftDepth=0,rightDepth = 0;
        TreeNode left = node.left;
        TreeNode right = node.right;
        while(right != null)
        {
            right = right.right;
            leftDepth++;
        }
        while(left != null)
        {
            left = left.left;
            leftDepth++;
        }
        if(leftDepth == rightDepth)
        {
            return (2>>leftDepth)-1;
        }

3.一層遞歸邏輯文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-718826.html

        int leftnum= getNum(node.left);
        int rightnum = getNum(node.right);
        int result = leftnum + rightnum+1;
        return result;

題目代碼:

class Solution {
    public int countNodes(TreeNode root) {
        return getNum(root);

    }
    public int getNum(TreeNode node)
    {
        //終止條件
        if(node == null)
        {
            return 0;
        }
        int leftDepth=0,rightDepth = 0;
        TreeNode left = node.left;
        TreeNode right = node.right;
        while(right != null)
        {
            right = right.right;
            leftDepth++;
        }
        while(left != null)
        {
            left = left.left;
            leftDepth++;
        }
        if(leftDepth == rightDepth)
        {
            return (2>>leftDepth)-1;
        }
        int leftnum= getNum(node.left);
        int rightnum = getNum(node.right);
        int result = leftnum + rightnum+1;
        return result;

    }
}

到了這里，關(guān)于代碼隨想錄 Day13 二叉樹(shù) LeetCode T104 二叉樹(shù)的最大深度 T111 二叉樹(shù)的最小深度 T222完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！