LeetCode 94 二叉树的中序遍历 [Swift]
2019-10-14
题目
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路
采用递归的方法比较直接，对二叉树进行递归遍历，代码实现如下：
class Solution {
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var ret = [Int]()
if root == nil {
return ret
}
traversal(root, valArray: &ret)
return ret
}
func traversal(_ root: TreeNode?, valArray : inout [Int]) {
if root == nil {
return
}
let right = root!.right
let left = root!.left
if left != nil {
traversal(left, valArray: &valArray)
}
valArray.append(root!.val)
if right != nil {
traversal(right, valArray: &valArray)
}
}
}
另外题目还提出了是否可以采用迭代算法解题。
为了求解，我们需要利用到 “栈” 的数据结构，首先对根节点的所有的左子节点进入入栈，然后出栈，对出栈的节点内容进行记录，记录完毕后，视出栈节点的右子树为根节点，进行之前同样的操作。代码实现如下：
class Solution {
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var ret = [Int]()
if root == nil {
return ret
}
var stack = [TreeNode]()
var curNode = root
while curNode != nil || stack.count != 0 {
while curNode != nil {
stack.append(curNode!)
curNode = curNode!.left
}
curNode = stack.popLast()
ret.append(curNode!.val)
curNode = curNode!.right
}
return ret
}
}