欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

劍指Offer之Java算法習(xí)題精講二叉樹的構(gòu)造和遍歷

 更新時間:2022年03月22日 09:19:42   作者:明天一定.  
跟著思路走,之后從簡單題入手,反復(fù)去看,做過之后可能會忘記,之后再做一次,記不住就反復(fù)做,反復(fù)尋求思路和規(guī)律,慢慢積累就會發(fā)現(xiàn)質(zhì)的變化

題目一

二叉樹題——最大二叉樹

根據(jù)給定的數(shù)組來構(gòu)建最大二叉樹

具體題目如下

 解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return method(nums,0,nums.length-1);
    }
    public TreeNode method(int[] nums,int lo,int hi){
        if(lo>hi){
            return null;
        }
        int index = -1;
        int max = Integer.MIN_VALUE;
        for(int i = lo;i<=hi;i++){
            if(max<nums[i]){
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = method(nums,lo,index-1);
        root.right = method(nums,index+1,hi);
        return root;
    }
}

題目二

二叉樹題——構(gòu)造二叉樹

根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回根節(jié)點

具體題目如下

 解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return method(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode method(int[] preorder, int preLeft,int preEnd , int[] inorder,int inLeft,int inEnd){
        if(preLeft>preEnd){
            return null;
        }
        int rootVal = preorder[preLeft];
        int index = -1;
        for(int i = inLeft;i<=inEnd;i++){
            if(rootVal == inorder[i]){
                index = i;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        int leftSize = index - inLeft;
        root.left = method(preorder,preLeft+1,leftSize+preLeft,inorder,inLeft,index-1);
        root.right = method(preorder,leftSize+preLeft+1,preEnd,inorder,index+1,inEnd);
        return root;
    }
}

題目三

二叉樹題——構(gòu)造二叉樹

根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回根節(jié)點

具體題目如下

 解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    TreeNode build(int[] inorder, int inStart, int inEnd,int[] postorder, int postStart, int postEnd) {
 
    if (inStart > inEnd) {
        return null;
    }
    // root 節(jié)點對應(yīng)的值就是后序遍歷數(shù)組的最后一個元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍歷數(shù)組中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    // 左子樹的節(jié)點個數(shù)
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(rootVal);
    // 遞歸構(gòu)造左右子樹
    root.left = build(inorder, inStart, index - 1,postorder, postStart, postStart + leftSize - 1);
    root.right = build(inorder, index + 1, inEnd,postorder, postStart + leftSize, postEnd - 1);
    return root;
}
}

題目四

二叉樹題——構(gòu)造二叉樹

根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回

具體題目如下

 解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return method(preorder,0,preorder.length-1,postorder,0,postorder.length-1);
    }
    public TreeNode method(int[] preorder,int preStart, int preEnd, int[] postorder,int postStart,int postEnd){
        if(preStart>preEnd){
            return null;
        }
        if(preStart==preEnd){
            return new TreeNode(preorder[preStart]);
        }
        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        int index = 0;
        for (int i = postStart; i < postEnd; i++) {
            if (postorder[i] == leftRootVal) {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        int leftSize = index - postStart + 1;
        root.left = method(preorder, preStart + 1, preStart + leftSize,postorder, postStart, index);
        root.right = method(preorder, preStart + leftSize + 1, preEnd,postorder, index + 1, postEnd - 1);
        return root;
    }
}

到此這篇關(guān)于劍指Offer之Java算法習(xí)題精講二叉樹的構(gòu)造和遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹構(gòu)造內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java用split分割含一個或多個空格的字符串案例

    Java用split分割含一個或多個空格的字符串案例

    這篇文章主要介紹了Java用split分割含一個或多個空格的字符串案例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來過來看看吧
    2020-09-09
  • 工廠方法在Spring框架中的運用

    工廠方法在Spring框架中的運用

    這篇文章介紹了工廠方法在Spring框架中的運用,文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-10-10
  • 解決SpringBoot2多線程無法注入的問題

    解決SpringBoot2多線程無法注入的問題

    這篇文章主要介紹了解決SpringBoot2多線程無法注入的問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-08-08
  • 為SpringBoot服務(wù)添加HTTPS證書的方法

    為SpringBoot服務(wù)添加HTTPS證書的方法

    這篇文章主要介紹了為SpringBoot服務(wù)添加HTTPS證書的方法,幫助大家更好的理解和使用springBoot框架,感興趣的朋友可以了解下
    2020-10-10
  • Eclipse安裝Aptana插件(注意對應(yīng)版本問題)

    Eclipse安裝Aptana插件(注意對應(yīng)版本問題)

    這篇文章主要為大家詳細介紹了Eclipse安裝Aptana插件的相關(guān)資料,特別注意對應(yīng)版本問題,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-02-02
  • struts2自定義MVC框架

    struts2自定義MVC框架

    這篇文章主要為大家詳細介紹了struts2如何自定義MVC框架,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-10-10
  • RocketMQ消費冪概念與使用分析

    RocketMQ消費冪概念與使用分析

    如果有?個操作,多次執(zhí)?與?次執(zhí)?所產(chǎn)?的影響是相同的,我們就稱這個操作是冪等的。當(dāng)出現(xiàn)消費者對某條消息重復(fù)消費的情況時,重復(fù)消費的結(jié)果與消費?次的結(jié)果是相同的,并且多次消費并未對業(yè)務(wù)系統(tǒng)產(chǎn)?任何負?影響,那么這整個過程就可實現(xiàn)消息冪等
    2023-02-02
  • java Class.getSimpleName() 詳解及用法

    java Class.getSimpleName() 詳解及用法

    這篇文章主要介紹了java Class.getSimpleName() 詳解及用法的相關(guān)資料,需要的朋友可以參考下
    2017-02-02
  • 一文教你學(xué)會搭建SpringBoot分布式項目

    一文教你學(xué)會搭建SpringBoot分布式項目

    這篇文章主要為大家詳細介紹了搭建SpringBoot分布式項目的相關(guān)知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01
  • 利用Jasypt如何對Spring Boot配置文件加密

    利用Jasypt如何對Spring Boot配置文件加密

    這篇文章主要給大家介紹了關(guān)于利用Jasypt如何對Spring Boot配置文件加密的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-07-07

最新評論