LeetCode初中级算法题解 - 二叉树篇
引言：
搜集题目的难度是在简单级别和中级级别，也是面试常考的题目。题目的题解，使用的开发语言是Swift。
因为题目的描述很长，以及有各种案例提示，为了不占篇幅，所以没有展示出来，大家可以直接通过题号查询，或者点击链接的形式去查看题目的描述。
文章的写作顺序是：1. 展示题号和以及题目的链接 2. 核心思想的讲述 3. 代码实现。
最后本文提供的代码都是在LeetCode上提交通过的。
Binary Tree Questions（二叉数相关问题）
1.LeetCode_144: 二叉树的前序遍历 2.LeetCode_102: 二叉树的层序遍历 3.LeetCode_104: 二叉树的最大深度 4.LeetCode_226: 翻转二叉树 5.LeetCode_110: 判断一个二叉树是不是平衡二叉树 6.LeetCode_101: 对称二叉树 7.LeetCode_100: 相同的树
1. 二叉树的前序遍历
1.1 核心思想:
二叉树的前、中、后序遍历是很简单的事情 前序遍历的顺序是：根、左、右。 递归实现，所以先访问根节点，然后再访问左子树、再访问右子树
1.2 代码实现:
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
nums.append(root.val)
preorderTraversal(root.left)
preorderTraversal(root.right)
return nums
}
那个中序遍历就应该这样写：
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
preorderTraversal(root.left)
nums.append(root.val)
preorderTraversal(root.right)
return nums
}
后序遍历就应该这样写：
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
preorderTraversal(root.left)
preorderTraversal(root.right)
nums.append(root.val)
return nums
}
2. 二叉树的层序遍历
2.1 核心思想:
二叉树的层序遍历真的非常非常的重要
二叉树的层序遍历的实现思路，用的是队列的特性，先进先出 首先根节点入队 然后出队列，然后将出队节点的左子树和右子树入队 这样达到的效果是，队列保存的是节点是每一层的节点
2.2 代码实现:
var results = [[Int]]()
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else{ return [] }
var queue = [TreeNode]()
queue.append(root)
while !queue.isEmpty {
var nums = [Int]()
for i in 0..<queue.count {
let node = queue.removeFirst()
nums.append(node.val)
if node.left != nil {
queue.append(node.left!)
}
if node.right != nil {
queue.append(node.right!)
}
}
results.append(nums)
}
return results
}
3. 二叉树的深度
3.1 核心思想:
使用层序遍历
3.2 代码实现:
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var queue = [TreeNode]()
queue.append(root)
var layer = 0
while !queue.isEmpty {
layer += 1
for i in 0..<queue.count {
let node = queue.removeFirst()
if node.left != nil {
queue.append(node.left!)
}
if node.right != nil {
queue.append(node.right!)
}
}
}
return layer
}
递归写法
func maxDepth(_ root: TreeNode?) -> Int {
if root == nil { return 0 }
return max(maxDepth(root?.left), maxDepth(root?.right)) + 1
}
4. 翻转二叉树
4.1 核心思想:
既然是翻转二叉树，那就访问到每一个节点，然后每一个节点的左右子树进行交换就好了。 既然要访问没一个节点，那就使用前中后或者层序遍历都可以呀。下面的算法是使用的前序遍历完成的。
4.2 代码实现:
func invertTree(_ root: TreeNode?) -> TreeNode? {
if root == nil { return root }
let temp = root?.left
root?.left = root?.right
root?.right = temp
invertTree(root?.left)
invertTree(root?.right)
return root
}
5. 判断一个二叉树是不是平衡二叉树
5.1 核心思想: 递归的思想
1.根据树的高度来判断 2.如果根节点的左右子树的高度差 <= 1, 并且左子树这棵树为平衡的，并且右子树这棵树也是平衡的， 则返回true。其他的返回false 递归的思想的极致使用。
5.2 代码实现:
func isBalanced(_ root: TreeNode?) -> Bool {
if root == nil { return true }
return abs(maxDepth(root?.left) - maxDepth(root?.right)) <= 1
&& isBalanced(root?.left)
&& isBalanced(root?.right)
}
func maxDepth(_ root: TreeNode?) -> Int {
if root == nil { return 0 }
return max(maxDepth(root?.left), maxDepth(root?.right)) + 1
}
6. 对称二叉树
6.1 核心思想:
左右子树相等，那就需要同时遍历左右子树，然后判断左右子树对应位置上的每一个节点的值都相等。
既然要遍历到每个节点，并且每次都是根节点先遍历到，我们可以使用前序遍历。
但是因为要同时遍历，所以我们创建一个方法func isMirror(_ left: TreeNode?, _ right: TreeNode?) -> Bool来同时遍历左右子树上对应位置上的节点
核心：这个递归的终止条件的设定是非常巧妙的
if left == nil && right == nil { return true }
if left == nil || right == nil { return false }
6.2 代码实现:
func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
return isMirror(root.left, root.right)
}
func isMirror(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
if left == nil && right == nil { return true }
if left == nil || right == nil { return false }
return (left!.val == right!.val)
&& isMirror(left?.left,right?.right) // 因为是对称的，所以是左vs右，和下面一道题的判断是不一样的
&& isMirror(left?.right, right?.left)
}
7. 相同的数
7.1 核心思想:
和第6题，是不是对称的树的求解思想，本质上是一样的。
7.2 代码实现:
func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
if p == nil && q == nil { return true }
if p == nil || q == nil { return false }
if p?.val != q?.val { return false }
return preorder(p, q)
}
func preorder(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
if p == nil && q == nil { return true }
if p == nil || q == nil { return false }
if p?.val != q?.val { return false }
if preorder(p?.left,q?.left) == false { return false }
if preorder(p?.right, q?.right) == false { return false }
return true
}
end
腾讯云开发者
