注：这一节练习 3 和练习 4 都是很经典的问题。
和二叉树相关的问题，在面试中是非常常见的。一旦我们熟悉了这些问题以后，会发现这些问题其实是非常简单的。
例题1：LeetCode 第 226 题：反转一棵二叉树
传送门：英文网址：226. Invert Binary Tree ，中文网址：226. 翻转二叉树 。
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9输出：
4 / \ 7 2 / \ / \ 9 6 3 1备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
分析：算法是非常重要的基本功。即使是大公司都非常注重基础问题的考察。
这道问题可以说是一个经典的问题。LeetCode 上有如下备注：
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
思路1：我们可以使用递归方法来完成，我们写好之后，会发现其实就是完成了一次深度优先遍历，并且是前序遍历，有的朋友可能写出来的后序遍历，那么我们不禁要问，中序遍历可不可以，答案是不可以，因为中序遍历很可能一个结点会被翻转两次，这与我们的要求是违背的。
Java 代码：
LeetCode 第 226 题：反转一棵二叉树
Python 代码：后序遍历
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
// swap root.left 和 root.right
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
}
Python 代码：与上面的代码等价
public class Solution2 {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}
练习1：LeetCode 第 100 题：判断两棵二叉树是否一样
传送门：英文网址：100. Same Tree ，中文网址：100. 相同的树 。
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true示例 2:
输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false示例 3:
输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
分析：判断两棵二叉树是否一样。这是典型的使用递归解决的问题。
Python 代码：
# Definition for a binary tree node.
# 判断两棵二叉树是否一样。
# 典型的使用递归解决的问题。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
if p is None:
return False
if q is None:
return False
return p.val == q.val and self.isSameTree(
p.left, q.left) and self.isSameTree(p.right, q.right)
练习2：LeetCode 第 101 题：判断两棵二叉树是否左右对称
传送门：英文网址：101. Symmetric Tree ，中文网址：101. 对称二叉树 。
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树
[1,2,2,3,4,4,3]是对称的。1 / \ 2 2 / \ / \ 3 4 4 3但是下面这个
[1,2,2,null,3,null,3]则不是镜像对称的:1 / \ 2 2 \ \ 3 3说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
思路1：递归处理，需要引入辅助函数。
Python 代码1：
# Definition for a binary tree node.
# 判断一棵二叉树是否镜面对称。
# 设置辅助函数是关键。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 还可以使用队列去完成
# https://leetcode.com/problems/symmetric-tree/solution/
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
return self.__helper(root.left, root.right)
def __helper(self, left_node, right_node):
if left_node is None and right_node is None:
return True
if left_node is None or right_node is None or left_node.val != right_node.val:
return False
return self.__helper(left_node.left, right_node.right) and self.__helper(
left_node.right, right_node.left)
思路2：非递归写法，借助双端队列辅助判断。自己画一个图，就好理解了。
LeetCode 第 101 题：判断两棵二叉树是否左右对称
Python 代码2：
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 非递归写法：借助双端队列辅助判断
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先写递归终止条件
if root is None:
return True
# 其实应该用 from collections import deque
deque = []
deque.insert(0, root.left)
deque.append(root.right)
while deque:
l_node = deque.pop(0)
r_node = deque.pop()
if l_node is None and r_node is None:
continue
if l_node is None or r_node is None:
return False
# 代码走到这里一定有 l_node 和 r_node 非空
# 因此可以取出 val 进行判断了
if l_node.val != r_node.val:
return False
deque.insert(0, l_node.right)
deque.insert(0, l_node.left)
deque.append(r_node.left)
deque.append(r_node.right)
return True
之前在刷这道题的时候，写过一个解法：先拷贝一棵二叉树，再反转，将反转以后的二叉树和自己比较，看看是否相等，这个思路就转化成了以前我们解决过的问题。另外复制的时候，我们可以反着复制，然后比较。
Java 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
TreeNode copyBinaryTree = copyBinaryTree(root);
TreeNode invertBinaryTree = invertBinaryTree(copyBinaryTree);
return isSameTree(root, invertBinaryTree);
}
private boolean isSameTree(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null || t1.val != t2.val) {
return false;
}
return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
}
private TreeNode invertBinaryTree(TreeNode node) {
if (node == null) {
return node;
}
invertBinaryTree(node.left);
invertBinaryTree(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
return node;
}
// 也使用递归的方式完成（熟悉一下如何完成二叉树的复制）
private TreeNode copyBinaryTree(TreeNode node) {
if (node == null) {
return null;
}
TreeNode newTreeNode = new TreeNode(node.val);
newTreeNode.left = copyBinaryTree(node.left);
newTreeNode.right = copyBinaryTree(node.right);
return newTreeNode;
}
}
练习3：LeetCode 第 222 题：求完全二叉树的节点数、满二叉树
传送门：222. 完全二叉树的节点个数。
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入: 1 / \ 2 3 / \ / 4 5 6 输出: 6
分析：给定一棵完全二叉树，求完全二叉树的节点的个数。
-
什么是完全二叉树？除了最后一层，所有层的节点数达到最大，与此同时，最后一层的所有节点集中在这一层的左侧。事实上，堆就是使用完全二叉树定义的。
-
什么是满二叉树？所有层的节点数达到了最大。
Python 代码：
# Definition for a binary tree node.
# 222. 完全二叉树的节点个数
# 给出一个完全二叉树，求出该树的节点个数。
# 说明：完全二叉树的定义如下：
# 在完全二叉树中，除了最底层节点可能没填满外，
# 其余每层节点数都达到最大值，
# 并且最下面一层的节点都集中在该层最左边的若干位置。
# 若最底层为第 h 层，则该层包含 1~ 2h 个节点。
# 求完全二叉树的结点数、满二叉树。使用递归可以完成。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
left_depth = self.__depth(root, True)
right_depth = self.__depth(root, False)
if left_depth == right_depth:
# return 2 ** left_depth - 1
return (1 << left_depth) - 1
if left_depth > right_depth:
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
def __depth(self, node, is_left):
depth = 0
while node:
depth += 1
node = node.left if is_left else node.right
return depth
说明：体会在递归过程中，“减而治之”的策略。
练习4：LeetCode 第 110 题：判断一棵二叉树是否是平衡二叉树
传送门：英文网址：110. Balanced Binary Tree ，中文网址：110. 平衡二叉树 。
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树
[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回
true。示例 2:
给定二叉树
[1,2,2,3,3,null,null,4,4]1 / \ 2 2 / \ 3 3 / \ 4 4返回
false。
分析：判断一棵二叉树是否是平衡二叉树。什么是平衡二叉树：每一个节点的左右子树的高度差不超过 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 给定一个二叉树，判断它是否是高度平衡的二叉树。
# 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先写特殊情况，空树是平衡二叉树
if root is None:
return True
return self.__helper(root) != -1
def __helper(self, node):
# 因为必须从底下到上面依次判断，所以使用后序遍历
if node is None:
return 0
left = self.__helper(node.left)
right = self.__helper(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
# 重点，辅助函数的定义是，左右子树的高度中最大的那个
return max(left, right) + 1
（本节完）
网友评论