剑指Offer之Java算法习题精讲二叉树的构造和遍历

题目一

 解法

/** * 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;    }}

题目二

 解法

/** * 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;    }}

题目三

 解法

/** * 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 节点对应的值就是后序遍历数组的最后一个元素    int rootVal = postorder[postEnd];    // rootVal 在中序遍历数组中的索引    int index = 0;    for (int i = inStart; i <= inEnd; i++) {        if (inorder[i] == rootVal) {            index = i;            break;        }    }    // 左子树的节点个数    int leftSize = index - inStart;    TreeNode root = new TreeNode(rootVal);    // 递归构造左右子树    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;}}

题目四

 解法

/** * 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算法习题精讲二叉树的构造和遍历的文章就介绍到这了,更多相关Java 二叉树构造内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 剑指Offer之Java算法习题精讲N叉树的遍历及数组与字符串

    题目一 解法 /* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class S

  • 剑指Offer之Java算法习题精讲数组与列表的查找及字符串转换

    题目一 解法 class Solution { public String toLowerCase(String s) { StringBuilder sb = new StringBuilder(); for(int i = 0;i<s.length();i++){ char ch = s.charAt(i); if('A'<=ch&&ch<='Z'){ ch = (char)(ch+32); } sb.append(ch); } return sb.toString(

  • 剑指Offer之Java算法习题精讲字符串与二叉搜索树

    题目一 解法 class Solution { public boolean repeatedSubstringPattern(String a) { for (int i = 1; i <=a.length()/2 ; i++) { String s = a.substring(0, i); StringBuffer sb = new StringBuffer(); while (sb.length()<a.length()){ sb.append(s); } if(sb.toString(

  • 剑指Offer之Java算法习题精讲数组与二叉树

    题目一  解法 /** * 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; *

  • 剑指Offer之Java算法习题精讲数组与字符串

    题目一  解法 class Solution { public int findLengthOfLCIS(int[] nums) { if(nums.length==1) return 1; int fast = 1; int tmp = 1; int max = Integer.MIN_VALUE; while(fast<nums.length){ if(nums[fast]>nums[fast-1]){ tmp++; max = Math.max(max,tmp); }else{ max

  • 剑指Offer之Java算法习题精讲数组与字符串题

    题目一 解法 class Solution { public int thirdMax(int[] nums) { Arrays.sort(nums); if(nums.length<3){ return nums[nums.length-1]; } int p = 1; for(int i =nums.length-2;i>=0;i--){ if(nums[i]==nums[i+1]){ }else{ ++p; if(p==3){ return nums[i]; } } } return n

  • 剑指Offer之Java算法习题精讲链表与字符串及数组

    题目一 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Soluti

  • 剑指Offer之Java算法习题精讲二叉树专项训练

    题目一  解法 /** * 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; *

  • 剑指Offer之Java算法习题精讲二叉树的构造和遍历

    题目一  解法 /** * 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; *

  • 剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二  解法 /** * Definition for a binary tree node. * public class TreeNode { * in

  • 剑指Offer之Java算法习题精讲二叉树与N叉树

    题目一  解法 /** * 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; *

  • 剑指Offer之Java算法习题精讲二叉树专题篇下

    题目一  解法 /** * 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; *

  • 剑指Offer之Java算法习题精讲二叉树专项解析

    题目一 解法 /** * 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; * t

  • 剑指Offer之Java算法习题精讲二叉树与链表

    题目一  解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root==null){ return true; }e

  • 剑指Offer之Java算法习题精讲二叉树专题篇上

    来和二叉树玩耍吧~ 题目一 解法 /** * 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

  • 剑指Offer之Java算法习题精讲链表专题篇

    题目一  解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solut

  • 剑指Offer之Java算法习题精讲数组与字符和等差数列

    题目一  解法 class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int[] arr = new int[1001]; int[] ans = new int[arr1.length]; int index = 0; for(int i =0;i<arr1.length;i++){ arr[arr1[i]]+=1; } for(int i = 0;i<arr2.length;i++){ while

随机推荐