前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指Offer第4题详解(附Java、Python源码)

剑指Offer第4题详解(附Java、Python源码)

作者头像
bboy枫亭
发布2020-09-22 11:07:58
4230
发布2020-09-22 11:07:58
举报
文章被收录于专栏:csdn_blog

1. 题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

2. 分析

(1)根据前序序列第一个结点确定根结点 (2)根据根结点在中序序列中的位置分割出左右两个子序列 (3)对左子树和右子树分别递归使用同样的方法继续分解

示例

代码语言:javascript
复制
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in

(1)根据当前前序序列的第一个结点确定根结点,为 1。 (2)找到 1 在中序遍历序列中的位置,为 in[3]。 (3)切割左右子树,则 in[3] 前面的为左子树, in[3] 后面的为右子树。则切割后的左子树前序序列为:{2,4,7},切割后的左子树中序序列为:{4,7,2};切割后的右子树前序序列为:{3,5,6,8},切割后的右子树中序序列为:{5,3,8,6}。 (4)对子树分别使用同样的方法分解(使用递归较方便)。

3. 代码实现

3.1 Java 实现

1.先来棵树

代码语言:javascript
复制
class TreeNode {
    int value;
    TreeNode leftTree;
    TreeNode rightTree;
    TreeNode(int x) { value = x; }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", leftTree=" + leftTree +
                ", rightTree=" + rightTree +
                '}';
    }
}
代码语言:javascript
复制
import java.util.Arrays;
public class JzOffer4 {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        // 先根据先序遍历建立根结点
        TreeNode root = new TreeNode(pre[0]);

        for (int i=0;i<in.length;i++) {
            if (in[i] == pre[0]) {
                /**
                 * 递归构建左右子树
                 * 注意 copyOfRange 函数,左闭右开
                 */
                root.leftTree = reConstructBinaryTree(Arrays.copyOfRange(pre, 1,i+1 ), Arrays.copyOfRange(in, 0, i));
                root.rightTree = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        System.out.println(new JzOffer4().reConstructBinaryTree(pre,in).toString());
    }
}

3.2 Python 实现

代码语言:javascript
复制
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        prelen = len(pre)
        tinlen = len(tin)
        if prelen == 0 | tinlen == 0 :
            return None
        root = TreeNode(pre[0])
        for i in range(tinlen):
            if tin[i] == pre[0]:
                root.left = self.reConstructBinaryTree(pre[1:i+1], tin[0:i])
                root.right = self.reConstructBinaryTree(pre[i+1:prelen], tin[i+1:tinlen])
                break
        return root
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/08/20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目描述
  • 2. 分析
  • 3. 代码实现
    • 3.1 Java 实现
      • 3.2 Python 实现
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档