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

根据一棵树的中序遍历与后序遍历构造二叉树。

思路:
根据后序遍历,先找到这棵树的根节点的值,也就是数组中最后一个节点(数组长度-1)的位置,由此创建根节点。
然后在中序遍历中找到根的值所在的下标,切出左右子树的前序和中序。
注意:如果后序遍历的数组长度为0,说明是一棵空树。
下面用具体的例子来说明:

中序:CDBAE
后序:DCBEA

1、由后序遍历可以确定A是这棵树的根节点,然后根据中序遍历切出A的左右子树,得到CDB属于A的左子树,E属于A的右子树,如下图:
《根据中序遍历和后序遍历构造二叉树》
2、接着以B为根节点,在中序遍历中再次切出B的左右子树,得到CD为B的左子树,右子树为空。
《根据中序遍历和后序遍历构造二叉树》
3、再以C为根节点,结合中序遍历,得到D为C的右子树,左子树为空。
《根据中序遍历和后序遍历构造二叉树》
创建好的二叉树如下图所示:
《根据中序遍历和后序遍历构造二叉树》
具体实现代码:

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

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

    private static int find(char[] array, int v) { 
        for (int i = 0; i < array.length; i++) { 
            if (array[i] == v) { 
                return i;
            }
        }
        return -1;
    }

    private static TreeNode buildTree(char[] inorder, char[] postorder) { 

        if (postorder.length == 0) { 
            return null;
        }

        //1、根据后序,找到根的值,并且创建根节点
        char rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);

        //2、在中序中找到根的值所在的下标
        int leftSize = find(inorder, rootValue);

        //3、切出左子树的中序和后序
        char[] leftInorder = Arrays.copyOfRange(inorder, 0, leftSize);
        char[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftSize);
        root.left = buildTree(leftInorder, leftPostorder);

        //4、切出右子树的中序和后序
        char[] rightInorder = Arrays.copyOfRange(inorder, leftSize+1, inorder.length);
        char[] rightPostorder = Arrays.copyOfRange(postorder, leftSize, postorder.length-1);
        root.right = buildTree( rightInorder,rightPostorder);

        return root;
    }

    public static void main(String[] args) { 
        char[] inorder = new char[]{ 'C', 'D', 'B', 'A', 'E'};
        char[] postorder = new char[]{ 'D', 'C', 'B', 'E', 'A'};
        TreeNode root = buildTree(inorder,postorder);
        System.out.println("创建成功");
    }
}
    原文作者:_Nanfeng
    原文地址: https://blog.csdn.net/Nan_Feng726/article/details/91050126
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞