课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > 给定二叉树的前序遍历和中序遍历
  • 给定二叉树的前序遍历和中序遍历

    发布:昆明Java培训      来源:达内新闻      时间:2016-09-08

  • 昆明Java培训班的老师今天给大家讲怎么生成二叉树。

    Example:

    前序遍历数组:preArr[]:{1,2,4,5,3,6,7}

    中序遍历数组:inArr[]:{4,2,5,1,6,3,7}

    解题思路:

    由二叉树的前序变量性质可知:preArr[0] 是数组的根节点,有根据二叉树的中序遍历的性质可知,{4,2,5}是二叉树的左子树,{6,3,7}在右子树上,重复执行该操作就构造出了二叉树

    public class Solution {

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

    TreeNode root = new TreeNode(pre[0]);//前序的第一个数定为根

    int len = pre.length;

    //当只有一个数的时候

    if (len == 1) {

    root.left = null;

    root.right = null;

    return root;

    }

    //找到中序中的根位置

    int rootval = root.val;

    int i;

    for (i = 0; i < len; i++) {

    if (rootval == in[i])

    break;

    }

    //创建左子树

    if (i > 0) {

    int[] pr = new int[i];

    int[] ino = new int[i];

    for (int j = 0; j < i; j++) {

    pr[j] = pre[j + 1];

    }

    for (int j = 0; j < i; j++) {

    ino[j] = in[j];

    }

    root.left = reConstructBinaryTree(pr, ino);

    } else {

    root.left = null;

    }

    //创建右子树

    if (len - i - 1 > 0) {

    int[] pr = new int[len - i - 1];

    int[] ino = new int[len - i - 1];

    for (int j = i + 1; j < len; j++) {

    ino[j - i - 1] = in[j];

    pr[j - i - 1] = pre[j];

    }

    root.right = reConstructBinaryTree(pr, ino);

    } else {

    root.right = null;

    }

    return root;

    }

    public static void main(String[] args) {

    int[] preArr = {1, 2, 4, 5, 3, 6, 7};

    int[] inArr = {4, 2, 5, 1, 6, 3, 7};

    Solution s = new Solution();

    TreeNode root = s.reConstructBinaryTree(preArr, inArr);

    s.postOrder(root);

    }

    了解详情请登陆昆明达内Java培训官网(km.Java.tedu.cn)!

    推荐文章

上一篇:基本问题解答

下一篇:java的线程终止

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:11/30

Java--零基础业余班

Java--零基础业余班

开班日期:11/30

Java--周末提升班

Java--周末提升班

开班日期:11/30

Java--零基础周末班

Java--零基础周末班

开班日期:11/30

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56