【二叉樹】二叉樹的中序周遊

0x00 周遊方式

二叉樹的周遊方式：

• 深度優先
• 廣度優先

深度優先：

• 前序周遊：​

  ​中​

  ​左右
• 中序周遊：左​

  ​中​

  ​右
• 後序周遊：左右​

  ​中​

  ​

廣度優先：

• 層序周遊：周遊完同一層的所有節點後，繼續往下層周遊

0x01 中序周遊

語言：​

​Swift​

​

樹節點：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func inorder(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    
    var array = [Int]()
    func dfs(_ root: TreeNode?) {
        guard let root = root else { return }
        dfs(root.left)         // 左
        array.append(root.val) // 中
        dfs(root.right)        // 右
    }
    
    dfs(root)
    return array
}      

func inorder(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    
    var array = [Int]()
    var stack = [TreeNode]()
    var t: TreeNode? = root
    
    while t != nil || !stack.isEmpty {
        while t != nil { // 先左，一直到最下邊
            stack.append(t!)  // 入棧       
            t = t!.left   //再下一個          // 左
        }
        
        if !queue.isEmpty {
            let node = queue.removeLast()
            array.append(node.val)           // 中
            // 進入右子樹，開始新的一輪左子樹周遊
            t = node.right                   // 右
        }
    }
    return array
}