二叉树相关
- 二叉树的遍历分为前序,中序,后序, 说白了就是根节点的位置, 根节点在前面就是前序遍历,以此类推
- 每种遍历各有优势, 比如获取某个二叉树的最大深度就采用前序遍历, 再比如获取所有节点个数就需要遍历整个二叉树, 此时采用后序遍历就比较合适, 只有二叉树才有中序遍历, 因为多叉树根节点的位置不确定.
- 中序遍历可以认为是遍历有序数组
题目1:
二叉树的最大深度
class Node {
var left: Node?
var right: Node?
var val: String
init(val: String) {
self.val = val
}
}
//解法1
var depth = 0, res = 0
func maxDepth(node: Node) -> Int {
reverse(node: node)
return res
}
func reverse(node: Node?) {
if node == nil {return}
depth += 1
if node?.left == nil, node?.right == nil {
res = Swift.max(depth, res)//到达叶子节点,
}
reverse(node: node?.left)
reverse(node: node?.right)
depth -= 1
}
//解法2
/// 输入根节点 返回二叉树的最大深度
/// - Parameter node: 输入根节点
/// - Returns: 最大深度
func reverse1(node: Node?) -> Int {
if node == nil {return 0}
let left = reverse1(node: node?.left)
let right = reverse1(node: node?.right)
res = Swift.max(left, right) + 1
return res
}
题目2:
如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
