Swift根据先序和中序确定一棵二叉树

Bertha 。 2022-05-11 11:44 113阅读 0赞

先序：12453687

后序：42518637

//
    //  TreeNode.swift
    //  Swift-Algorithm
    //
    //  Created by Seven on 2018/10/19.
    //  Copyright © 2018年 seven. All rights reserved.
    //
    
    import UIKit
    
    class TreeNode: NSObject {
        var val: String
        var left: TreeNode?
        var right: TreeNode?
        
        init(_ val: String) {
            self.val = val;
        }
        
        func initAuto() -> TreeNode{
           let root = TreeNode("G")
           let D = TreeNode("D")
           let A = TreeNode("A")
            let E = TreeNode("E")
            let F = TreeNode("F")
            let M = TreeNode("M")
            let H = TreeNode("H")
            let Z = TreeNode("Z")
            
            root.left = D
            D.left = A
            D.right = F
            F.left = E
            
            root.right = M
            M.left = H
            M.right = Z
            
            return root
        }
        
        
    }
    
    extension TreeNode {
        //MARK: - 遍历
        /// 先序遍历
        func preOrder (_ root: TreeNode?) {
            if root != nil {
                print("\(root!.val)")
                preOrder(root!.left)
                preOrder(root!.right)
            }
        }
        
        //MARK: - 翻转
        /// 翻转二叉树
        func reverseLeftAndRight(_ root: TreeNode?) -> TreeNode? {
            
            guard let root = root else {
                return nil
            }
            
    //        let temp = root.left
    //        root.left = reverseLeftAndRight(root.right)
    //        root.right = reverseLeftAndRight(temp)
            
            (root.left,root.right) = (reverseLeftAndRight(root.right),reverseLeftAndRight(root.left))
            return root
        }
        
        //MARK: - 非递归中序
        /// 非递归中序遍历
        func midOrder(_ root: TreeNode?)->[String] {
            var res = [String]()
            var stack = [TreeNode]()
            
            var node = root
            
            while !stack.isEmpty || node != nil {
                if node != nil {
                    stack.append(node!)
                    node = node!.left
                }else {
                    if (stack.count > 0) {
                        node = stack.removeLast()
                        res.append(node!.val)
                        node = node!.right
                    }
                }
            }
            
            return res
            
            
        }
        
        
        /// 树的深度
        func maxDeep(_ root: TreeNode?) -> Int {
            guard let root = root else {
                return 0
            }
            
            return max(maxDeep(root.left)+1, maxDeep(root.right)+1)
        }
        
        /// 树的层级遍历
        func levelOrder(_ root: TreeNode?) ->[[String]]?{
            var res = [[String]]()
            var list = [TreeNode]()
            
            if let root = root {
                list.append(root)
            }
            
            
            while !list.isEmpty {
                var temp = [String]()
                let size = list.count
                
                for _ in 0..<size {
                    let node = list.removeFirst()
                    temp.append(node.val)
                    
                    if node.left != nil {
                        list.append(node.left!)
                    }
                    if node.right != nil {
                        list.append(node.right!)
                    }
                    
                }
                res.append(temp)
            }
            print(res)
            return res;
            
        }
        
        //MARK: - 知道两种顺序，确定唯一树
        
        func creaTree(_ preOrder: [String]?, _ midOrder: [String]?) -> TreeNode? {
            guard let preOrder = preOrder else {
                return nil
            }
            
            guard let midOrder = midOrder else {
                return nil
            }
            
            guard let root = findRoot(preOrder, midOrder) else {
                return nil
            }
            devide(midOrder, root, preOrder)
            
            return root
            
        }
        
        // 根据前序查找根
        fileprivate func findRoot(_ preOrderArr: [String], _ sourArr:[String]) -> TreeNode?{
            var index = preOrderArr.count
            for str in sourArr {
                if let atIndex = preOrderArr.firstIndex(of: str) {
                    if atIndex <= index {
                        index = atIndex
                    }
                }
            }
            if index == preOrderArr.count {
                return nil
            }
            let node = TreeNode(preOrderArr[index])
            return node
        }
        
        // 递归拆分左右
        fileprivate func devide(_ leftArr: [String], _ left: TreeNode, _ preOrderArr: [String]) {
            if (leftArr.count>0) {
                if let atIdx = leftArr.firstIndex(of: left.val) {
                    var tempPre = [String]()
                    var tempPost = [String]()
                    for (i, str) in leftArr.enumerated() {
                        
                        if i<atIdx {
                            tempPre.append(str)
                        }else if (i>atIdx) {
                            tempPost.append(str)
                        }
                    }
                    
                    if tempPre.count > 0 {
                        let leftNode = findRoot(preOrderArr, tempPre)
                        left.left = leftNode
                        devide(tempPre, leftNode!, preOrderArr)
                    }
                    
                    if tempPost.count > 0 {
                        let rightNode = findRoot(preOrderArr, tempPost)
                        left.right = rightNode
                        devide(tempPost, rightNode!, preOrderArr)
                    }
                    
                }
            }
        }
    
    }

测试：

let res =  root.creaTree(["G","D","A","F","E","M","H","Z"], ["A","D","E","F","G","H","M","Z"]);
            
            let res2 = root.creaTree(["1","2","4","5","3","6","8","7"], ["4","2","5","1","8","6","3","7"])