来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
题目
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
swift，先定义出TreeNode。值，左节点，右节点。中序遍历的顺序是左-根-右。
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
}
}
方法1-递归
func inorderTraversal(_ root: TreeNode?) -> [Int] {
if (root != nil) {
inorderTraversal(root!.left)
if ((root?.val) != nil) {
result.append(root!.val)
}
inorderTraversal(root!.right)
}
return result
}
方法2-栈处理
struct Stack {
var stackArr = [TreeNode]()
var count: Int {
return stackArr.count
}
mutating func push(node: TreeNode) -> Void {
stackArr.append(node)
}
mutating func pop() -> TreeNode {
return stackArr.popLast()!
}
}
class Solution {
var result = [Int]()
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var curNode = root
var stack = Stack()
while curNode != nil || stack.count != 0{
//先找左边的节点，放入栈中
while curNode != nil {
stack.push(node: curNode!)
curNode = curNode?.left
}
//取出栈中的最后一个
curNode = stack.pop()
//将值放入数组
result.append(curNode!.val)
//找右边的节点。也是先找左边节点，放入栈中。
curNode = curNode?.right
}
return result
}
}
最后
本文用了两种方法实现，递归和栈~如果有更好的，欢迎大家一块儿讨论
