服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 剑指Offer之Java算法习题精讲二叉树的构造和遍历

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

2022-10-13 12:54明天一定. Java教程

跟着思路走，之后从简单题入手，反复去看，做过之后可能会忘记，之后再做一次，记不住就反复做，反复寻求思路和规律，慢慢积累就会发现质的变化

题目一

二叉树题——最大二叉树

根据给定的数组来构建最大二叉树

具体题目如下

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

 解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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;
    }
}

题目二

二叉树题——构造二叉树

根据给定的数组按照指定遍历条件构造二叉树并返回根节点

具体题目如下

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

 解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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;
    }
}

题目三

二叉树题——构造二叉树

根据给定的数组按照指定遍历条件构造二叉树并返回根节点

具体题目如下

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

 解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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;
}
}

题目四

二叉树题——构造二叉树

根据给定的数组按照指定遍历条件构造二叉树并返回

具体题目如下

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

 解法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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 二叉树构造内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/wai_58934/article/details/123054330

  • Java
  • 遍历
  • 二叉树
  • 构造

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    501 　 406 　 415 　 2000 　 1433 　 401 　 330 　 204 　 选择排序法 　 随机抽取 　 内存卡 　 下载器 　 十六进制字符 　 响应 　 静态工厂 　 构造函数 　 swt 　 Overview 　 对象池模式 　 InterProcessMutex 　 支票 　 金额大写转换 　 空心菱形 　 AspectJ 　 面向切面编程 　 方法名 　 网址信息 　 动态代理模式 　 线程安全 　 htmlparser 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图