【数据结构】二叉树构造《LintCode072和LintCode073》

学而不思则罔，思而不学则殆

【数据结构】二叉树构造《LintCode072和LintCode073》

• 整理思路
• LitCode073
• LintCode072

---

整理思路

通过前序或者后序便找到根节点，找到根节点后在中序遍历数组中根据根节点把数组划分为两个数组，分别是左子树的中序遍历结果，另一个是右子树的中序遍历结果。依次类推，可以构造一颗二叉树。

LitCode073

https://www.lintcode.com/problem/construct-binary-tree-from-preorder-and-inorder-traversal/description

描述
根据前序遍历和中序遍历树构造二叉树.

算法结果

算法实现

package data.structure.tree;

/**
 * 有前序序列和中序数列构造二叉树
 */
public class LintCode0073 {

    //Definition of TreeNode:
    private static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public static void main(String[] args) {
        int[] pre = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] in = new int[]{4, 2, 5, 1, 6, 3, 7};
        int[] post = new int[]{4, 2, 5, 1, 6, 3, 7};
        LintCode0073 lintCode0073 = new LintCode0073();
        TreeNode root = lintCode0073.buildTree(pre, in);
        System.out.println(root);
    }




    /**
     * @param preorder : A list of integers that preorder traversal of a tree
     * @param inorder  : A list of integers that inorder traversal of a tree
     * @return : Root of a tree
     * 根据前序遍历和中序遍历确定一颗二叉树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // write your code here
        TreeNode[] treeNodes = new TreeNode[2];
        buildTreePreAndIn(preorder, 0, preorder.length, inorder, 0, inorder.length, treeNodes, 0);

        return treeNodes[0];
    }

    //[preStart,preEnd)  [intStart,inEnd)

    /**
     * @param preorder 前序遍历的数组
     * @param preStart 前序遍历开始位置
     * @param preEnd   前序遍历结束位置
     * @param inorder  中序遍历数组
     * @param inStart  中序遍历开始位置
     * @param inEnd    中序遍历结束位置
     * @param parents  父节点
     * @param flag     0 计算根节点  1 父节点的做左孩子 2 计算父节点的右孩子
     * @return
     */
    public void buildTreePreAndIn(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, TreeNode[] parents, int flag) {
        System.out.println("[" + preStart + "," + preEnd + "] [" + inStart + "," + inEnd + "] flag " + flag);
        if (preEnd == preStart) { //没有元素
            return;
        } else if (preStart == preEnd - 1) { //只有一个元素
            TreeNode treeNode = new TreeNode(preorder[preStart]);
            if (flag == 0) {
                parents[0] = treeNode;
            } else if (flag == 1) {
                parents[1].left = treeNode;
            } else {
                parents[1].right = treeNode;
            }
            return;
        } else {//多个元素
            //根据前序遍历的第一个节点确定根节点
            int tmpRootValue = preorder[preStart];

            TreeNode tmpRoot = new TreeNode(tmpRootValue);
            if (flag == 0) {
                parents[0] = tmpRoot;
            } else if (flag == 1) {
                parents[1].left = tmpRoot;
            } else if (flag == 2) {
                parents[1].right = tmpRoot;
            }
            parents[1] = tmpRoot;

            int index = inStart; //根节点在中序遍历中的位置
            for (int i = inStart; i < inEnd; i++) {
                if (tmpRootValue == inorder[i]) {
                    index = i;
                    break;
                }
            }


            // FIXME: 2020/11/1 check中遍历中数组是否正确
            //根据该位置把中序遍历划分为两个部分 [inStart,index) index [index+1,inEnd)

            System.out.println("tmpRootValue:" + tmpRootValue + " index:" + index);
            //划分数组
            //中序遍历的划分的数组 [0,flag-1][flag][flag+1,inorder.length-1]
            //两个子树属于递归逻辑
            //计算左子树
            //1.没有左孩子
            //2.只有一个左孩子
            //3.左子树有两个以上的元素
            if (inStart == index) {
                //没有左子树
            } else if (inStart == index - 1) {
                parents[1].left = new TreeNode(inorder[inStart]);
            } else {
                //左元素个数
                int num = index - inStart;
                //前序序列
                int tmpPreStart = preStart + 1;
                int tmpPreEnd = tmpPreStart + num;

                //中序序列
                int tmpInStart = inStart;
                int tmpInEnd = index;

                buildTreePreAndIn(preorder, tmpPreStart, tmpPreEnd, inorder, tmpInStart, tmpInEnd, parents.clone(), 1);
            }

            //计算右子树
            //1.没有右子树
            //2.只有一个右孩子
            //2.右子树有两个元素
            //3.右子树有两个以上的元素
            if (index == inEnd - 1) {
                //没有左子树 do Nothing
            } else if (index == inEnd - 2) {
                parents[1].right = new TreeNode(inorder[index + 1]);
            } else {
                //中序序列
                int tmpInStart = index + 1;
                int tmpInEnd = inEnd;

                //左元素个数
                int num = tmpInEnd - tmpInStart;
                //前序序列的右子树部分
                int tmpPreEnd = preEnd;
                int tmpPreStart = preEnd - num;

                buildTreePreAndIn(preorder, tmpPreStart, tmpPreEnd, inorder, tmpInStart, tmpInEnd, parents.clone(), 2);
            }
        }
    }

}

LintCode072

https://www.lintcode.com/problem/construct-binary-tree-from-inorder-and-postorder-traversal/description

描述
根据中序遍历和后序遍历树构造二叉树

算法结果

算法实现

package data.structure.tree;

public class LintCode0072 {
    //Definition of TreeNode:
    private static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public static void main(String[] args) {
        int[] pre = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] in = new int[]{4, 2, 5, 1, 6, 3, 7};
        int[] post = new int[]{4, 2, 5, 1, 6, 3, 7};
        LintCode0072 lintCode0072 = new LintCode0072();
        //TreeNode root = treeMain002.buildTree1(pre, in);
        TreeNode root = lintCode0072.buildTree(in, post);
        System.out.println(root);
    }


    /**
     * @param inorder:   A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     * //后序遍历和中序遍历求二叉树
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // write your code here
        // write your code here
        TreeNode[] treeNodes = new TreeNode[2];
        buildTreeInAndPost(postorder, 0, postorder.length, inorder, 0, inorder.length, treeNodes, 0);

        return treeNodes[0];
    }

    //[postStart,postEnd) [inStart,inEnd)
     /**
     * @param postorder 后序遍历的数组
     * @param postStart 后序遍历开始位置
     * @param postEnd   后序遍历结束位置
     * @param inorder   中序遍历数组
     * @param inStart   中序遍历开始位置
     * @param inEnd     中序遍历结束位置
     * @param parents   父节点
     * @param flag      0 计算根节点  1 父节点的做左孩子 2 计算父节点的右孩子
     * @return
     */
    private void buildTreeInAndPost(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd, TreeNode[] parents, int flag) {
        System.out.println("[" + postStart + "," + postEnd + "] [" + inStart + "," + inEnd + "] flag " + flag);
        if (postStart == postEnd) { //没有元素
            return;
        } else if (postStart == postEnd - 1) { //只有一个元素
            TreeNode treeNode = new TreeNode(postorder[postStart]);
            if (flag == 0) {
                parents[0] = treeNode;
            } else if (flag == 1) {
                parents[1].left = treeNode;
            } else {
                parents[1].right = treeNode;
            }
            return;
        } else {//多个元素
            //根据后序遍历的最后一个节点确定根节点
            int tmpRootValue = postorder[postEnd - 1];

            TreeNode tmpRoot = new TreeNode(tmpRootValue);
            if (flag == 0) {
                parents[0] = tmpRoot;
            } else if (flag == 1) {
                parents[1].left = tmpRoot;
            } else if (flag == 2) {
                parents[1].right = tmpRoot;
            }
            parents[1] = tmpRoot;

            int index = inStart; //根节点在中序遍历中的位置
            for (int i = inStart; i < inEnd; i++) {
                if (tmpRootValue == inorder[i]) {
                    index = i;
                    break;
                }
            }

            // FIXME: 2020/11/1 check中遍历中数组是否正确
            //根据该位置把中序遍历划分为两个部分 [inStart,index) index [index+1,inEnd)

            System.out.println("tmpRootValue:" + tmpRootValue + " index:" + index);
            //划分数组
            //中序遍历的划分的数组 [0,flag-1][flag][flag+1,inorder.length-1]
            //两个子树属于递归逻辑
            //计算左子树
            //1.没有左孩子
            //2.只有一个左孩子
            //3.左子树有两个以上的元素
            if (inStart == index) {
                //没有左子树
            } else if (inStart == index - 1) {
                parents[1].left = new TreeNode(inorder[inStart]);
            } else {
                //左子树元素个数
                int num = index - inStart;
                //中序序列
                int tmpInStart = inStart;
                int tmpInEnd = index;

                //前序序列
                int tmpPostStart = postStart;
                int tmpPostEnd = tmpPostStart + num;


                buildTreeInAndPost(postorder, tmpPostStart, tmpPostEnd, inorder, tmpInStart, tmpInEnd, parents.clone(), 1);
            }

            //计算右子树
            //1.没有右子树
            //2.只有一个右孩子
            //2.右子树有两个元素
            //3.右子树有两个以上的元素
            if (index == inEnd - 1) {
                //没有左子树 do Nothing
            } else if (index == inEnd - 2) {
                parents[1].right = new TreeNode(inorder[index + 1]);
            } else {
                //中序序列
                int tmpInStart = index + 1;
                int tmpInEnd = inEnd;

                //左元素个数
                int num = tmpInEnd - tmpInStart;
                //前序序列的右子树部分
                int tmpPostEnd = postEnd - 1;
                int tmpPreStart = tmpPostEnd - num;

                buildTreeInAndPost(postorder, tmpPreStart, tmpPostEnd, inorder, tmpInStart, tmpInEnd, parents.clone(), 2);
            }
        }
    }
}