程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 二叉樹 根據二叉樹的前序數組和中序序遍歷數組生成二叉樹,歷數二叉樹

二叉樹 根據二叉樹的前序數組和中序序遍歷數組生成二叉樹,歷數二叉樹

編輯: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);
    }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved