【面试】重建二叉树

简介: 笔记

一、描述


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

class BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode m_pLeft;
    BinaryTreeNode m_pRight;
    public BinaryTreeNode(int m_nValue, BinaryTreeNode m_pLeft, BinaryTreeNode m_pRight) {
        this.m_nValue = m_nValue;
        this.m_pLeft = m_pLeft;
        this.m_pRight = m_pRight;
    }
}


二、解题思路


可以根据前序遍历序列结合中序遍历序列找到某个结点的左子树和右子树,从而使用递归完成求解。


三、代码


package com.hust.grid.leesf.chapter2;
import java.util.Scanner;
class BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode m_pLeft;
    BinaryTreeNode m_pRight;
    public BinaryTreeNode(int m_nValue, BinaryTreeNode m_pLeft, BinaryTreeNode m_pRight) {
        this.m_nValue = m_nValue;
        this.m_pLeft = m_pLeft;
        this.m_pRight = m_pRight;
    }
}
public class ConstructBinaryTree {
    public static BinaryTreeNode construct(int[] preOrder, int[] inOrder, int length) throws Exception {
        if (preOrder == null || inOrder == null || length <= 0) {
            return null;
        }
        return constructCore(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }
    public static BinaryTreeNode constructCore(int[] preOrder, int startPreIndex, int endPreIndex,
                                               int[] inOrder, int startInIndex, int endInIndex) throws Exception {
        int rootValue = preOrder[startPreIndex];
        BinaryTreeNode root = new BinaryTreeNode(rootValue, null, null);
        // 只有一个元素,为递归的出口
        if (startPreIndex == endPreIndex) {
            if (startInIndex == endInIndex
                    && preOrder[startPreIndex] == inOrder[startInIndex]) {
                return root;
            } else {
                throw new Exception("invalid input");
            }
        }
        // 在中序遍历中找到根结点
        int rootInIndex = startInIndex;
        while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
            ++rootInIndex;
        }
        if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
            throw new Exception("invalid input");
        }
        int leftLength = rootInIndex - startInIndex;
        int leftPreOrderEndIndex = startPreIndex + leftLength;
        if (leftLength > 0) {
            // 构建左子树
            root.m_pLeft = constructCore(preOrder, startPreIndex + 1,
                    leftPreOrderEndIndex, inOrder, startInIndex,
                    rootInIndex - 1);
        }
        if (leftLength < endPreIndex - startPreIndex) {
            // 右子树存在元素,构建右子树
            root.m_pRight = constructCore(preOrder, leftPreOrderEndIndex + 1,
                    endPreIndex, inOrder, rootInIndex + 1, endInIndex);
        }
        return root;
    }
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        String preOrderInput = scan.nextLine();
        String inOrderInput = scan.nextLine();
        int[] preOrder = new int[preOrderInput.length()];
        int[] inOrder = new int[inOrderInput.length()];
        for (int index = 0; index < preOrderInput.length(); index++) {
            preOrder[index] =  Integer.parseInt(String.valueOf(preOrderInput.charAt(index)));
        }
        for (int index = 0; index < inOrderInput.length(); index++) {
            inOrder[index] = Integer.parseInt(String.valueOf(inOrderInput.charAt(index)));
        }
        BinaryTreeNode root = construct(preOrder, inOrder, preOrder.length);
        preOrderTraverse(root);
        System.out.println();
        inOrderTraverse(root);
        System.out.println();
        postOrderTraverse(root);
    }
    public static void preOrderTraverse(BinaryTreeNode root) {
        if (root != null) {
            System.out.print(root.m_nValue + " ");
            preOrderTraverse(root.m_pLeft);
            preOrderTraverse(root.m_pRight);
        }
    }
    public static void inOrderTraverse(BinaryTreeNode root) {
        if (root != null) {
            inOrderTraverse(root.m_pLeft);
            System.out.print(root.m_nValue + " ");
            inOrderTraverse(root.m_pRight);
        }
    }
    public static void postOrderTraverse(BinaryTreeNode root) {
        if (root != null) {
            postOrderTraverse(root.m_pLeft);
            postOrderTraverse(root.m_pRight);
            System.out.print(root.m_nValue + " ");
        }
    }
}

输入结果:

12473568
47215386

输出结果:

1 2 4 7 3 5 6 8 
4 7 2 1 5 3 8 6 
7 4 2 5 8 6 3 1 
目录
相关文章
|
2月前
数据结构之二叉树及面试题讲解(二)
数据结构之二叉树及面试题讲解
33 0
|
2月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
24 0
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
2月前
|
算法 C++
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
24 0
|
2月前
|
算法 Java C++
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
30 0
【面试小知识】带你深入了解二叉树的前中序遍历
【面试小知识】带你深入了解二叉树的前中序遍历
|
2月前
|
算法 Java 程序员
【Java程序员面试专栏 数据结构篇】五 高频面试算法题:二叉树
【Java程序员面试专栏 数据结构篇】五 高频面试算法题:二叉树
45 0
|
7月前
|
算法 C语言 C++
LeetCode | 二叉树高频面试算法题汇总【速来】-2
LeetCode | 二叉树高频面试算法题汇总【速来】
42 0