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

更新時間：2022年03月22日 09:19:42 作者：明天一定.

跟著思路走，之后從簡單題入手，反復去看，做過之后可能會忘記，之后再做一次，記不住就反復做，反復尋求思路和規(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é)點對應的值就是后序遍歷數(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;
    }
}

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

您可能感興趣的文章: