linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

重建二叉树

时间:2017-10-19  来源:未知  作者:admin666

题目:输入某二叉树的前序遍历黑夜中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历中都不包含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历 {4, 7, 2, 1, 5, 3, 8, 6},则重建出该二叉树。

C#实现:

public class BinaryTreeNode
    {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
 
        public static BinaryTreeNode Construct(ArrayList preorder, ArrayList inOrder)
        {
            if (preorder == null || inOrder == null || preorder.Count != inOrder.Count
                || preorder.Count <=0 || inOrder.Count <=0)
                return null;
            return ConstructCore(preorder, inOrder);
        }
 
        public static BinaryTreeNode ConstructCore(ArrayList preorder, ArrayList inOrder)
        {
            int rootValue = (int)preorder[0];
 
            BinaryTreeNode root = new BinaryTreeNode();
            root.value = rootValue;
 
            int pos = inOrder.IndexOf(rootValue);
            if (pos > 0) // 根值的左边还有元素
            {
                root.left = ConstructCore(preorder.GetRange(1, pos), inOrder.GetRange(0, pos));
            }
            if (pos < inOrder.Count - 1) // 根值的右边还有元素
            {
                root.right = ConstructCore(preorder.GetRange(pos + 1, preorder.Count - pos - 1),
                    inOrder.GetRange(pos + 1, inOrder.Count - pos - 1));
            }
            return root;
        }
        }

Java实现:

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
 
    // 输入某二叉树的前序遍历黑夜中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历
    // 中都不包含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历
    // {4, 7, 2, 1, 5, 3, 8, 6},则重建出该二叉树
    public static BinaryTreeNode Construct(List<Integer> preOrder, List<Integer> inOrder) {
        if (preOrder == null || inOrder == null || preOrder.size() != inOrder.size() || preOrder.size() <= 0
                || inOrder.size() <= 0)
            return null;
        return ConstructCore(preOrder, inOrder);
    }
 
    public static BinaryTreeNode ConstructCore(List<Integer> preOrder, List<Integer> inOrder) {
        int rootValue = preOrder.get(0);
 
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = rootValue;
 
        int pos = inOrder.indexOf(rootValue);
        if (pos > 0) // 根值的左边还有元素
        {
            root.left = ConstructCore(preOrder.subList(1, pos+1),
                    inOrder.subList(0, pos));
        }
        if (pos < inOrder.size() - 1) // 根值的右边还有元素
        {
            root.right = ConstructCore(preOrder.subList(pos + 1, preOrder.size()),
                    inOrder.subList(pos + 1, inOrder.size()));
        }
        return root;
    }
    }

Python实现:

class BinaryTree(object):
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
 
    def rebuild(self, preOrder, inOrder):
        if preOrder == None or inOrder == None or len(preOrder) <=0 or len(inOrder) <=0 \
                or len(preOrder) != len(inOrder):
            return None
        cur = BinaryTree(preOrder[0])
        index = inOrder.index(preOrder[0])
        cur.left = self.rebuild(preOrder[1: index+1], inOrder[:index])
        cur.right = self.rebuild(preOrder[index+1:], inOrder[index+1:])
        return cur

友情链接