【面试】重建二叉树

简介: 笔记

一、描述


输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树,假设输入的前序遍历和中序遍历的结果中都不含重复的数字,例如输入前序遍历序列{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 
目录
打赏
0
0
0
0
38
分享
相关文章
|
8月前
|
C++
二叉树进阶面试题(精华总结)【C++版本】
二叉树进阶面试题(精华总结)【C++版本】
|
8月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
52 0
|
4月前
|
二叉树面试题
本文介绍了二叉树相关的几个经典算法问题。首先讲解了如何判断两棵树是否完全相同(LeetCode 100),并给出了代码示例。接着讨论了如何判断一棵树是否是另一棵树的子树(LeetCode 572),详细分析了子树的定义及判断方法。然后介绍了翻转二叉树(LeetCode 226)的实现方法,即在遍历时交换每个节点的左右子树。随后探讨了如何判断一棵树是否是对称的(LeetCode 101),通过对左右子树的递归比较来实现。最后分析了平衡二叉树的概念(LeetCode 110)及判断方法,并给出了优化后的代码示例。此外,还简要介绍了二叉树遍历及二叉树最近公共祖先(LeetCode 236)的问题
31 6
二叉树面试题
|
2月前
|
JAVA 二叉树面试题
JAVA 二叉树面试题
22 0
|
8月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
8月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
8月前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
8月前
|
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
44 0
|
8月前
|
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
50 0
|
8月前
数据结构之二叉树及面试题讲解(三)
数据结构之二叉树及面试题讲解(三)
49 0

热门文章

最新文章