Leetcode 530. 二叉搜索樹的最小絕對差

題目鏈接: 二叉搜索樹的最小絕對差
自己的思路:和驗(yàn)證二叉搜索樹一樣的思路！可以求每個相鄰節(jié)點(diǎn)的差值的絕對值，然后和之前的差值的絕對值進(jìn)行比較，取最小的為新的res；遞歸三部曲：1、傳入?yún)?shù)：當(dāng)前節(jié)點(diǎn)；2、終止條件：如果當(dāng)前節(jié)點(diǎn)為空，直接返回；3、單層遞歸邏輯：中序遍歷??！因?yàn)橹行虮闅v可以保證是遞增的，這樣就不會跳著比較，所以先遞歸左子樹，然后中節(jié)點(diǎn)和前一個節(jié)點(diǎn)求差值的絕對值和res比較，取最小值為res，然后再定義新的pre，再進(jìn)行右子樹的遍歷即可?。。?/p>

正確思路:

代碼:

class Solution {
    int res = Integer.MAX_VALUE;
    TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        if (root==null) return 0;
        getmin(root);
        return res;
    }
    
    public void getmin(TreeNode root){
        if (root==null) return;
        //左遞歸
        getmin(root.left);
        //求上一個節(jié)點(diǎn)和此節(jié)點(diǎn)的最小值和之前的差進(jìn)行比較
        if (pre!=null){
            res = Math.min(res,Math.abs(pre.val-root.val));
        }
        //重新表示上一個節(jié)點(diǎn)
        pre = root;
        //右遞歸
        getmin(root.right);
    }
}

復(fù)雜度分析：
時間復(fù)雜度：$\mathcal{O}(n)$
空間復(fù)雜度：$\mathcal{O}(1)$

Leetcode 501. 二叉搜索樹中的眾數(shù)

題目鏈接: 二叉搜索樹中的眾數(shù)
自己的思路:沒想到?。。?！

正確思路:比較笨的方法是遍歷兩次二叉樹，然后找其中最大的值就可以；但是這里是使用了一點(diǎn)代碼技巧來處理這個問題，所以使用一次遍歷就可以；具體的思路為：二叉搜索樹一定是中序遍歷?。。?！這樣可以保證有序，主要是處理中的邏輯，我們可以定義三個變量，count用于存儲當(dāng)前結(jié)點(diǎn)的值出現(xiàn)的次數(shù)，maxcount用于存儲出現(xiàn)的最多的結(jié)點(diǎn)出現(xiàn)的次數(shù)，pre存儲上一個節(jié)點(diǎn)；首先是計(jì)數(shù)階段：當(dāng)pre是空的時候，那也就是說node現(xiàn)在是出于葉子節(jié)點(diǎn)，記錄它的count值為1，當(dāng)pre的結(jié)點(diǎn)值等于node的結(jié)點(diǎn)值的時候，說明出現(xiàn)了相同的節(jié)點(diǎn)值，則count++，當(dāng)pre的結(jié)點(diǎn)值不等于node的結(jié)點(diǎn)值時，說明出現(xiàn)了不同的節(jié)點(diǎn)值，重置count為1；然后是加入結(jié)果階段：當(dāng)count==maxcount的時候，說明當(dāng)前的次數(shù)和最大的次數(shù)相同，當(dāng)前結(jié)點(diǎn)值加入到結(jié)果集中，如果count>maxcount的時候，說明之前的maxcount并不是全局的最大，所以把之前的res中的所有元素清空，然后再加入新的結(jié)果，并且把maxcount賦值為count；遞歸三部曲：1、傳入?yún)?shù)：當(dāng)前節(jié)點(diǎn)；2、終止條件：當(dāng)當(dāng)前節(jié)點(diǎn)為空的時候，返回；3、單層邏輯：先左遞歸，然后處理中間節(jié)點(diǎn)，然后右遞歸！?。?/p>

代碼:

class Solution {
    List<Integer> res = new ArrayList<>();
    int count = 0;
    int maxcount = 0;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        addMode(root);
        int [] re = new int[res.size()];
        for (int i =0;i<re.length;i++){
            re[i] = res.get(i);
        }
        return re;
    }
    public void addMode(TreeNode node){
        if (node==null) return;
        addMode(node.left);

        //計(jì)數(shù)階段
        if (pre==null) count=1;
        else if (pre.val==node.val){
            count++;
        }
        else count=1;

        //加結(jié)果階段
        if (count>maxcount){
            maxcount = count;
            res.clear();
            res.add(node.val);
        }else if (count==maxcount){
            res.add(node.val);
        }
        pre = node;
        addMode(node.right);
    }
}

復(fù)雜度分析：
時間復(fù)雜度：$\mathcal{O}(n)$
空間復(fù)雜度：$\mathcal{O}(1)$

Leetcode 236. 二叉樹的最近公共祖先

題目鏈接: 二叉樹的最近公共祖先
自己的思路:沒想到?。?！

正確思路:主要是遍歷順序，使用后序遍歷出來，自底向上地返回；遞歸三部曲：1、傳入?yún)?shù)：當(dāng)前結(jié)點(diǎn)、結(jié)點(diǎn)p、結(jié)點(diǎn)q；2、終止條件：當(dāng)當(dāng)前結(jié)點(diǎn)是空或者p和q時，直接返回當(dāng)前結(jié)點(diǎn)即可，因?yàn)闆]有比這個更深的結(jié)點(diǎn)了；3、單層遞歸邏輯：先左右遞歸左右子樹查找左右子樹分別對p和q的最近公共祖先，得到left和right，如果兩個都為空，說明沒找到，直接返回null，如果其中一個不為空，另一個為空，說明不為空的那個為最近公共祖先，如果兩個都不為空，則當(dāng)前節(jié)點(diǎn)為最近公共祖先?。?！
代碼:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果當(dāng)前結(jié)點(diǎn)就是空或者p和q的話，直接返回當(dāng)前結(jié)點(diǎn)
        if (root==null||root==p||root==q){
            return root;
        }
        //遞歸左右子樹
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //如果左右兩邊都沒有，直接返回null
        if (left==null&&right==null) return null;
        //左邊有返回左邊，右邊有返回右邊
        if (left==null||right==null){
            return left==null?right:left;
        }
        //左右兩邊都有返回當(dāng)前結(jié)點(diǎn)
        return root;
    }
}

復(fù)雜度分析：
時間復(fù)雜度：$\mathcal{O}(n)$
空間復(fù)雜度：$\mathcal{O}(1)$文章來源地址http://www.zghlxwxcb.cn/news/detail-597592.html

到了這里，關(guān)于代碼隨想錄第二十一天的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！