Binary Tree Inorder Traversal

题目介绍

LeetCode 94. Binary Tree Inorder Traversal。

复杂度

时间复杂度: O(n), 空间复杂度: O(n)

解题思路

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

class Solution {
    // 递归
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else {
            return []
        }
        var ans: [Int] = []
        ans += inorderTraversal(root.left)
        ans.append(root.val)
        ans += inorderTraversal(root.right)
        return ans
    }
    // 迭代
    func inorderTraversal1(_ root: TreeNode?) -> [Int] {
        guard let root = root else {
            return []
        }
        var ans: [Int] = []
        var stack: [TreeNode] = []
        var node: TreeNode? = root
        while !stack.isEmpty || node != nil {
            //不断往左子树方向走，每走一次就将当前节点保存到栈中
            while node != nil {
                stack.append(node!)
                node = node!.left
            }
            // 当走到空的时候，加入 ans，继续遍历右子树
            node = stack.popLast()
            ans.append(node!.val)
            node = node!.right
        }
        return ans
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/04/10/BinaryTreeInorderTraversal/