欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树前序中序后序

程序员文章站 2024-01-15 21:57:16
...

前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)
中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)
后序遍历:左子树 —> 右子树 —> 根结点(最后遍历根节点

前序序列{1,2,4,7,3,5,6,8}
中序序列{4,7,2,1,5,3,8,6}
前序序列的第一个结点确定根结点,为 1
找1在中序的位置,左子树前序序列为:{2,4,7},切割后的左子树中序序列为:{4,7,2};切割后的右子树前序序列为:{3,5,6,8},切割后的右子树中序序列为:{5,3,8,6} 。
循环二叉树前序中序后序
二叉树前序中序后序

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

import java.util.Arrays;
public class Solution {
    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.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树,注意 copyOfRange 函数,左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }
}