第 08 关 | 二叉树的深度优先经典问题:1.青铜挑战——二叉树的经典算法题-灵析社区
时光小少年1. 二叉树的双指针
1.1. 判断两棵树是否相同
LeetCode100：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入：p = [1,2,3], q = [1,2,3]
输出：true
输入：p = [1,2], q = [1,null,2]
输出：false
这个貌似就是两个二叉树同时进行前序遍历，先判断根节点是否相同， 如果相同再分别判断左右子节点是否相同，判断的过程中只要有一个不相同就返回 false，如果全部相同才会返回true。其实就是这么回事。看代码：
public boolean isSameTree(TreeNode p, TreeNode q) {
//如果都为空我们就认为他是相同的
if (p == null && q == null)
return true;
//如果一个为空，一个不为空，很明显不可能是相同的树，直接返回false即可
if (p == null || q == null)
return false;
//如果对应位置的两个结点的值不相等，自然也不是同一个棵树
if (p.val != q.val)
return false;
//走到这一步说明节点p和q是完全相同的，接下来需要再判断其左左和右右是否满足要求了
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
def isSameTree(self, p, q):
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
else:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
bool isSameTree( TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) {
return true;
} else if (p == NULL || q == NULL) {
return false;
} else if (p->val != q->val) {
return false;
} else {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
本题除了上述方式，还可以使用广度优先，感兴趣的同学可以试一试。
1.2. 对称二叉树
LeetCode101 给定一个二叉树，检查它是否是镜像对称的。例如下面这个就是对称二叉树：
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是对称的:
1
/ \
2 2
\ \
3 3
如果树是镜像的，下面这个图更直观一些：
因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等，所以准确的来说是一个树的遍历顺序是左右中，一 个树的遍历顺序是右左中。这里的关键还是如何比较和如何处理结束条件。 单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称:传入的是左节点的左孩子，右节点的右孩子。
- 比较 内侧是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
接下来就是合并和进一步简化：
class Solution {
//主方法
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return check(root.left, root.right);
}
public boolean check(TreeNode p,TreeNode q){
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if( p.val != q.val){
return false;
}
return check(p.left, q.right) && check(p.right, q.left);
}
}
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
if(p->val != q->val) return false;
return check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
class Solution(object):
def isSymmetric(self, root):
if not root:
return True
def dfs(left,right):
if not (left or right):
return True
if not (left and right):
return False
if left.val!=right.val:
return False
return dfs(left.left,right.right) and dfs(left.right,right.left)
# 用递归函数，比较左节点，右节点
return dfs(root.left,root.right)
1.3. 合并二叉树
LeetCode617.给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
输入:
Tree 1: Tree 2:
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出合并后的树:
3
/ \
4 5
/ \ \
5 4 7
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
● 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
● 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
● 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并：
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode merged = new TreeNode(t1.val + t2.val);
merged.left = mergeTrees(t1.left, t2.left);
merged.right = mergeTrees(t1.right, t2.right);
return merged;
}
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) {
return t2;
}
if (t2 == nullptr) {
return t1;
}
auto merged = new TreeNode(t1->val + t2->val);
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}
class Solution:
def mergeTrees(self, t1, t2) :
if not t1:
return t2
if not t2:
return t1
merged = TreeNode(t1.val + t2.val)
merged.left = self.mergeTrees(t1.left, t2.left)
merged.right = self.mergeTrees(t1.right, t2.right)
return merged
如果这个感觉还是想不明白，可以直接对照题干给的例子来验证一下。
最后我们来造个题：前面我们研究了两棵树相等和一棵树对称的情况，我们可以造一道题，判断两棵树是否对称的。如下就是一个对称的二叉树，那该如何写代码实现呢？请你思考。
2. 路径专题
关于二叉树有几道与路径有关的题目，我们统一看一下。初次接触你会感觉有些难，但是这是在为回溯打基础，因为很多回溯问题就是在找路径，甚至要找多条路径。
2.1. 二叉树的所有路径
LeetCode257：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
我们可以注意到有几个叶子节点，就有几条路径，那如何找叶子节点呢？我们知道深度优先搜索就是从根节点开始一直找到叶子结点，我们这里可以先判断当前节点是不是叶子结点，再决定是不是向下走，如果是叶子结点，我们就增加一条路径，就像下面图中这样：
这里还有个问题，当得到一个叶子结点容易，那这时候怎么知道它所在的完整路径是什么呢？例如上图中得到D之后，怎么知道其前面的A和B呢？简单，增加一个String类型的变量中，访问每个节点访问的时候先存到String中，到叶子节点的时候再添加到集合里 :
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, "", res);
return res;
}
void dfs(TreeNode root, String path, List<String> res) {
if (root == null) return;
if (root.left == null && root.right == null) {
res.add(path + root.val);
return;
}
dfs(root.left, path + root.val + "->", res);
dfs(root.right, path + root.val + "->", res);
}
void construct_paths(TreeNode* root, string path, vector<string>& paths) {
if (root != nullptr) {
path += to_string(root->val);
if (root->left == nullptr && root->right == nullptr) { // 当前节点是叶子节点
paths.push_back(path); // 把路径加入到答案中
} else {
path += "->"; // 当前节点不是叶子节点，继续递归遍历
construct_paths(root->left, path, paths);
construct_paths(root->right, path, paths);
}
}
}
//主方法入口
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
construct_paths(root, "", paths);
return paths;
}
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
def construct_paths(root, path):
if root:
path += str(root.val)
if not root.left and not root.right: # 当前节点是叶子节点
paths.append(path) # 把路径加入到答案中
else:
path += '->' # 当前节点不是叶子节点，继续递归遍历
construct_paths(root.left, path)
construct_paths(root.right, path)
paths = []
construct_paths(root, '')
return paths
本题可以作为回溯的入门问题，我们到回溯时再讲解。
2.2. 路径总和
上面我们讨论的找所有路径的方法，那我们是否可以再找一下哪条路径的和为目标值呢？这就是LeetCode112题：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum。叶子节点 是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
输入：root = [1,2,3], targetSum = 5
输出：false
本题询问是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum，假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
不难发现这满足递归的性质，若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum == root.val;
}
boolean left= hasPathSum(root.left, sum - root.val) ;
boolean right=hasPathSum(root.right, sum - root.val);
return left|| right;
}
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr) {
return false;
}
if (root->left == nullptr && root->right == nullptr) {
return sum == root->val;
}
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
class Solution:
def hasPathSum(self, root, sum):
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
本题还有个拓展，既然找到是否存在路径了，那能把找到的路径打印出来吗？当然可以，这就是LeetCode113题，我们将本题做为入门题在回溯部分讲解。
3. 翻转的妙用
来看 LeetCode226 翻转二叉树，将二叉树整体反转。如下图所示：
这个题也是剑指offer27题的要求，根据上图，可以发现想要翻转树，就是把每一个节点的左右孩子交换一下。关键在于遍历顺序，前中后序应该选哪一种遍历顺序。遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。
这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
先看前序交换：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
def invertTree(self, root):
if root == None:
return None
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return root
TreeNode* invertTree1( TreeNode* root) {
if (root == NULL) {
return NULL;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invertTree1(root->left);
invertTree1(root->right);
return root;
}
再看后序：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
class Solution(object):
def invertTree(self,root):
if root == None:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
这道题目使用前序遍历和后序遍历都可以，主要区别是是前序是先处理当前节点再处理子节点，是自顶向下，后序是先处理子结点最后处理自己，一个是自下而上的。观察下图就明白了：
本题还可以使用层次遍历实现，核心思想是元素出队时，先将其左右两个孩子不是直接入队，而是先反转再放进去，代码如下：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if (tmp.left != null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if (tmp.right != null) {
queue.add(tmp.right);
}
}
return root;
}
}
class Solution(object):
def invertTree(self, root):
if not root:
return None
# 将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
queue = [root]
while queue:
# 每次都从队列中拿一个节点，并交换这个节点的左右子树
tmp = queue.pop(0)
tmp.left,tmp.right = tmp.right,tmp.left
# 如果当前节点的左子树不为空，则放入队列等待后续处理
if tmp.left:
queue.append(tmp.left)
# 如果当前节点的右子树不为空，则放入队列等待后续处理
if tmp.right:
queue.append(tmp.right)
# 返回处理完的根节点
return root
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right); // 节点处理
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
阅读量：1691
点赞量：0
收藏量:0