【数据结构与算法】二叉树的遍历与构造

本文主要是介绍【数据结构与算法】二叉树的遍历与构造，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

根据先序和中序构建二叉树

测试样例：

先序：3,9,20,15,7

中序：9,3,15,20,7

结果：3,9,20,null,null,15,7

二叉树结构：

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

①递归写法

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0)
            return null;
        TreeNode root = new TreeNode(preorder[0]);
        int rootIndex = 0;
        while (inorder[rootIndex] != preorder[0]) {
            rootIndex++;
        }
        int len1 = rootIndex;
        int len2 = preorder.length - len1 - 1;

        TreeNode leftTree = null;
        TreeNode rightTree  = null;

        int[] leftPreOrder = new int[len1];
        int[] leftInOrder = new int[len1];
        int[] rightPreOrder = new int[len2];
        int[] rightInOrder = new int[len2];

        if(len1!=0) {
            for (int i = 0; i < len1;i++) {
                leftInOrder[i] = inorder[i];
                leftPreOrder[i] = preorder[i+1];
            }
            leftTree = buildTree(leftPreOrder, leftInOrder);
        }
        if(len2!=0) {
            for (int i = 0; i < len2; i++) {
                rightInOrder[i] = inorder[i + rootIndex + 1];
                rightPreOrder[i] = preorder[i + rootIndex + 1];
            }
            rightTree = buildTree(rightPreOrder, rightInOrder);
        }
        root.left = leftTree;
        root.right = rightTree;
        return root;
    }

代码写的有点乱，大题思路是每次在先序序列中找到根节点并构建，然后根据根节点在中序序列的位置，能够确定左子树节点个数len1、右子树节点个数len2以及左右子树的划分。则递归进行对左右子树的构建，然后将根节点指针指向左右子树。

比较烦人的点就是数组下标的确定：

preOrder：左子树(1,len1) 右子树(len1+1,len1+len2)

inOrder：左子树(0,len1-1)右子树(len1,len1+len2)

②非递归写法

这篇关于【数据结构与算法】二叉树的遍历与构造的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！