之前的文章中關(guān)于二叉樹(shù)的先序遍歷，中序遍歷丈秩，后序遍歷盯捌，層次遍歷，當(dāng)然我們可以根據(jù)二叉樹(shù)的先序和中序蘑秽， 重構(gòu)二叉樹(shù)饺著，輸出后序，也可以根據(jù)二叉樹(shù)的中序和后序肠牲，輸出先序~

先序和中序重構(gòu)

定義二叉樹(shù)的先序幼衰，中序和后序:

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"]

二叉樹(shù)重構(gòu):

    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
        //獲取中序數(shù)組中的根節(jié)點(diǎn)位置
        for index in 0..<inOrder.count {
            if inOrder[index] == preOrder[0] {
                rootIndex = index
                break
            }
        }
        
        //先序左子樹(shù) 中序的左子樹(shù)
        for i in 0..<rootIndex {
            pre_left.append(preOrder[i+1])
            in_left.append(inOrder[i])
        }
        
        //先序的右子樹(shù) 中序的右子樹(shù)
        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
    }

中序和后序重構(gòu)

    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
        //獲取中序數(shù)組中的根節(jié)點(diǎn)位置
        for index in 0..<inOrder.count {
            if inOrder[index] == postOrder[postOrder.count-1] {
                rootIndex = index
                break
            }
        }
        
        //中序左子樹(shù) 后序的左子樹(shù)
        for i in 0..<rootIndex {
            in_left.append(inOrder[i])
            post_left.append(postOrder[i])
        }
        //中序的右子樹(shù) 后序的右子樹(shù)
        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
    }

代碼測(cè)試:

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