之前的文章中关于二叉树的先序遍历，中序遍历，后序遍历，层次遍历，当然我们可以根据二叉树的先序和中序， 重构二叉树，输出后序，也可以根据二叉树的中序和后序，输出先序~

先序和中序重构

定义二叉树的先序，中序和后序:

var rePreOrder:[String] = ["1","2","4","7","3","5","6","8"]
var reInOrder:[String] = ["4","7","2","1","5","3","8","6"]
var rePostOrder:[String] = ["7","4","2","5","8","6","3","1"]

二叉树重构:

    func reConstructForPost(preOrder: [String],inOrder: [String]) -> TreeNode? {

        if inOrder.count == 0 {
            return nil
        }
        var pre_left:[String] = []
        var pre_right:[String] = []
        var in_left:[String] = []
        var in_right:[String] = []

        let root = TreeNode()
        root.data = preOrder[0] as NSString
        
        var rootIndex = 0
        //获取中序数组中的根节点位置
        for index in 0..<inOrder.count {
            if inOrder[index] == preOrder[0] {
                rootIndex = index
                break
            }
        }
        
        //先序左子树 中序的左子树
        for i in 0..<rootIndex {
            pre_left.append(preOrder[i+1])
            in_left.append(inOrder[i])
        }
        
        //先序的右子树 中序的右子树
        for j in rootIndex+1..<inOrder.count {
            pre_right.append(preOrder[j])
            in_right.append(inOrder[j])
        }
        
        root.leftChild=reConstructForPost(pre_left, inOrder: in_left)
        root.rightChild=reConstructForPost(pre_right, inOrder: in_right)
        
        return root
    }

中序和后序重构

    func reConstructForPre(inOrder: [String],postOrder: [String]) -> TreeNode? {
        
        if inOrder.count == 0 {
            return nil
        }

        var in_left:[String] = []
        var in_right:[String] = []
        var post_left:[String] = []
        var post_right:[String] = []
        
        let preRoot = TreeNode()
        preRoot.data = postOrder[postOrder.count-1] as NSString
        
        var rootIndex = 0
        //获取中序数组中的根节点位置
        for index in 0..<inOrder.count {
            if inOrder[index] == postOrder[postOrder.count-1] {
                rootIndex = index
                break
            }
        }
        
        //中序左子树 后序的左子树
        for i in 0..<rootIndex {
            in_left.append(inOrder[i])
            post_left.append(postOrder[i])
        }
        //中序的右子树 后序的右子树
        for j in rootIndex+1..<inOrder.count {
            in_right.append(inOrder[j])
            post_right.append(postOrder[j-1])
        }
        
        preRoot.leftChild=reConstructForPre(in_left, postOrder: post_left)
        preRoot.rightChild=reConstructForPre(in_right, postOrder: post_right)
        
        return preRoot
    }

代码测试:

var constructTree = ConstructBinaryTree()
var rePreOrder:[String] = ["1","2","4","7","3","5","6","8"]
var reInOrder:[String] = ["4","7","2","1","5","3","8","6"]
var rePostOrder:[String] = ["7","4","2","5","8","6","3","1"]
var constructRoot = constructTree.reConstructForPost(rePreOrder, inOrder: reInOrder)
print("FlyELephant")
print("先序和中序输出后序:")
postOrder(constructRoot)

var preRoot = constructTree.reConstructForPre(reInOrder, postOrder: rePostOrder)
print("\n中序和后序输出先序:")
preOrder(preRoot)
print("")

FlyElephant.png