swift-treenode

//: Playground - noun: a place where people can play

import UIKit


import UIKit
class   TreeNode{
    var  value:Int!
    var  left:TreeNode?
    var  right:TreeNode?
    init(_ x:Int) {
        self.value = x
    }
}
class Solution {
    static   var  lastsequence = [TreeNode]()
    /// 还原二叉树
    ///
    /// - Parameters:
    ///   - pre: 前序序列    abcdefg
    ///   - mid: 中序序列
    /// - Returns: 返回二叉树
    static  func  resumeNodeTree(_ pre:[Int],_ mid:[Int]) -> TreeNode?{
        if  pre.count == 0 || mid.count == 0 || pre.count != mid.count{
            
            assert(true, "前序序列或中序序列输入不正确")
            return nil
        }
        //找到根节点
        let   rootnode = TreeNode(pre[0])
        //用于存储待递归的左子树中序序列
        var    leftin = [Int]()
        //用于存储待递归的左子树的前序序列
        var  leftpre = [Int]()
        //用于存储待递归的右子树中序序列
        var  rightin = [Int]()
        //用于存储待递归的右子树前序序列
        var  rightpre = [Int]()
        
        // 前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
        // 该树还原         1
        //               /  \
        //              2    3
        //             /    /  \
        //            4    5    6
        //             \        /
        //              7      8
        //
        // 后序遍历的序列则为 7 4 2 5 8 6 3 1  到此还原完成  还原的过程则是后序遍历的序列
        // 找出根节点在中序序列的位置索引
        var   rootpos  = 0
        for   i in 0 ..< mid.count {
            if  mid[i] == pre[0]{
                rootpos = i
            }
        }
        //左边部分为左子树 构建左子树的前序序列和中序序列
        for  i in 0..<rootpos{
            leftin.append(mid[i])
            leftpre.append(pre[i+1])
        }
        //右边边部分为右子树 构建右子树的前序序列和中序序列
        for  i in rootpos+1..<mid.count{
            rightin.append(mid[i])
            rightpre.append(pre[i])
        }
        //递归查找左子树
        rootnode.left  = resumeNodeTree(leftpre, leftin)
        //递归查找右子树
        rootnode.right  = resumeNodeTree(rightpre, rightin)
        //到此位置整个二叉树的还原就是后序遍历 类似告诉前中后的原理一样 任意的给两个序列，倒推的过程就是剩下的序列遍历
        lastsequence.append(rootnode)
        return  rootnode
    }
    
}
//深度遍历
func   bfsscanNode(node:TreeNode?) {
    //递归方式也可以使用栈的方式
    if node != nil  {
        print(node?.value)
        if  node?.left != nil {
        bfsscanNode(node: node?.left)
        }
        if  node?.right != nil {
        bfsscanNode(node: node?.right)
        }
    }
    
}
//广度遍历
func   dfsscanNode(node:TreeNode?){
    //使用队列的方式 添加完到队列然后出队列
    var   aquene = [TreeNode]()
    
    if  node != nil {
    //当前所在层次
        var   cur_level = 1
        //当前层次多少个元素
        var   cur_levelnumber = 1
        //下一层多少个元素
        var  next_levelnumber = 0
        
        aquene.append(node!)
        while !aquene.isEmpty {
            
            let curnode = aquene.first
             print(curnode?.value)
            print("当前层数:\(cur_level)")
            cur_levelnumber = cur_levelnumber - 1
            if  curnode?.left != nil {
                
                aquene.append(curnode!.left!)
                next_levelnumber = next_levelnumber + 1
            }
            if  curnode?.right != nil {
            
                aquene.append(curnode!.right!)
                next_levelnumber = next_levelnumber + 1
            }
          
            if  0 == cur_levelnumber {
                cur_levelnumber = next_levelnumber
                next_levelnumber = 0
                cur_level = cur_level + 1
                
            }
            
            
            aquene.removeFirst()
            
            
            
        }
    }
}



var  rootnode:TreeNode? = Solution.resumeNodeTree([1,2,4,7,3,5,6,8], [4,7,2,1,5,3,8,6])
if  rootnode != nil {
     var  prenode = rootnode
  
    print("//------后序遍历------//")
    for  node in Solution.lastsequence{
        print(node.value)
    }
    //深度遍历
    print("//-------深度遍历-----//")
    bfsscanNode(node: prenode)
    //广度遍历
    print("//-------广度遍历-----//")
    dfsscanNode(node: prenode)
}

效果
//------后序遍历------//
7
4
2
5
8
6
3
1
//-------深度遍历-----//
Optional(1)
Optional(2)
Optional(4)
Optional(7)
Optional(3)
Optional(5)
Optional(6)
Optional(8)
//-------广度遍历-----//
Optional(1)
当前层数:1
Optional(2)
当前层数:2
Optional(3)
当前层数:2
Optional(4)
当前层数:3
Optional(5)
当前层数:3
Optional(6)
当前层数:3
Optional(7)
当前层数:4
Optional(8)
当前层数:4