1. 对称和反转专题

在上一篇文章中的三个问题都需要先知道左右子树的情况才能处理自己当前的结果，这本质都是后序遍历，那前序什么时候会用呢？本小节就好几个。

LeetCode100：给你两棵二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。

LeetCode617 合并两个二叉树，给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠，此时计算其和。

LeetCode101 给定一个二叉树，检查它是否是镜像对称的。

LeetCode226 翻转二叉树，将二叉树整体反转

这四个题，本质上也是一样的，都是需要两个指针额外，这两个指针可能针对一棵树，也可能针对两棵树。所以我们还是放在一起来分析。

1.1 判断两棵树是否相同

LeetCode100：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1：
输入：p = [1,2,3], q = [1,2,3] 
输出：true

示例2：
输入：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;
	//如果这两个节点都不为空并且又不相等，所以他也不可能是相同的树，直接返回false 
	if (p.val != q.val)
		return false;
	//走到这一步说明节点p和q是完全相同的，我们只需要在比较他们的左右子节点即可
	return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

这里用中序或者后序行不行呢？理论是上可以的，感兴趣的可以试一试。

1.2 合并两棵树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为
NULL的节点将直接作为新二叉树的节点。

示例  1: 输入 :
Tree 1                     Tree 2
    1                             2
   / \                           / \
  3   2                         1   3
 /                               \   \
5                                 4   7
输出 :
合并后的树 :
    3
   / \
  4   5
 / \   \
5   4   7

这个题看似复杂，很多人疑惑的点是如何同时遍历两个二叉树呢？其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作，将只处理一个二叉树的普通的前中后序，变成能同时处理两个树就行了。

可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。 两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

• 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
• 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
• 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和， 此时需要显性合并两个节点。

对一个节点进行合并之后，还要对该节点的左右子树分别进行合并：

class Solution {
	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;
	}
}

如果这个感觉还是想不明白，可以直接对照题干给的例子来验证一下。

1.3 对称二叉树

LeetCode101 给定一个二叉树，检查它是否是镜像对称的。例如下面这个就是对称二叉树：

     1
    / \
   2   2
  / \ / \
 3  4 4  3

但是下面这个[1,2,2,null,3,null,3]则不是对称的:

     1
    / \
   2   2
    \   \
     3   3

因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等，所以准确的来说是一个树的遍历顺序是左右中，一 个树的遍历顺序是右左中。这都可以理解算是后序遍历，尽管已经不是严格的后序遍历了。

那么我们来看看递归法的代码应该怎么写，注意我们比较的其实不是当前节点的左孩子和右孩子，所以如下我们称之为左节点右节点，left和right。对于二叉树如果对称，则left和right应该满足：

if (left == NULL && right != NULL)
	return false;
else if (left != NULL && right == NULL)
	return false;
else if (left == NULL && right == NULL)
	return true;
else if (left->val != right->val)
	return false; // 注意这里不能使用else

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

1. 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
2. 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
3. 如果左右都对称就返回true ，有一侧不对称就返回false 。

代码如下，注意compare括号里的内容如何设置的:

// 左子树:左、  右子树:右
bool outside = check(left.left, right.right); 
// 左子树:右、  右子树:左
bool inside = check(left.right, right.left); 
// 左子树:中、  右子树:中(逻辑处理)
bool isSame = outside && inside;
return isSame;

如上面代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为 “后序遍历”(尽管不是严格的后序遍历)。接下来就是合并和进一步简化：

返回ture的两个条件：

1. 都为null
2. left.value=right.value & Symmetric（left.left， right.right） && Symmetric（left.right， right.left）

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null){
			return true;
		}
		return check(root, root);
	}

	public boolean check(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		}
		if (p == null || q == null) {
			return false;
		}
		return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
	}
}

上面这个代码有一个地方会让人感觉迷惑，在isSymmetric中，为什么要用 check(root, root)呢？直接判断check(root.left, root.right)不香吗？如果直接改成这样子，正常的case也能执行的，但是问题是你需要增加判空的代码，也就是root可能为空， root.left 、root.right也可能为空，这时候就要增加一堆的判断逻辑，也就是：

public static boolean isSymmetric(TreeNode root) {
	if (root == null) {
		return true;
	}
	if (root.left == null && root.right == null) {
		return true;
	}
	if (root.left == null || root.right == null) {
		return false;
	}
	return check(root.left, root.right);
}

这时候你会发现check中也进行了类似的判断，是否重复了呢？所以我们就使用check(root, root)，将重复的工作都放到check里，这样就让代码更加精简。

这个过程也是我们思考算法的过程，先一步步分析，不要怕代码重复啰嗦，先各个击破，最后会发现很多判断逻辑等可以合并和简化，这样就成了一个比较好的算法。

我在面试遇到复杂逻辑的时候，我通常的做法是先大胆写，不管是否好看，第一版出来之后，重写一版再给面试官看。这个题还可以用迭代方式进行，但是面试的时候能用递归方式写出来就行了，我们节省一下脑细胞继续看其他题。

1.4 翻转二叉树

LeetCode226 翻转二叉树，将二叉树整体反转。如下图所示：

这个题也是剑指offer27题的要求。这个题不仅仅是访问了，还要修改二叉树的指针，因此处理起来要更加小心。

根据上面的图，可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。关键在于遍历顺序，前中后序应该选哪一种遍历顺序? (一些同学这道题都过了，但是不知道自己用的 是什么顺序)。遍历的过程中去翻转 每一个节点的左右孩子就可以达到整体翻转的效果。注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

先看前序交换：

class Solution {
	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		TreeNode temp=root.left;
		root.left=root.right;
		root.right=temp;

		TreeNode left = invertTree(root.left);
		TreeNode right = invertTree(root.right);
		return root;
	}
}

再看后序：

class Solution {
	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;
	}
}

这道题目使用前序遍历和后序遍历都可以，用层次遍历也可以。中序遍历是不行的，感兴趣的可以研究一下。

这里的区别非常小，主要就是先翻转还是先访问左右子树。所以上面的翻转一个是自顶向下，一个是自下而上的。

1.5 我们来造题：两个树是对称的

前面我们研究了两棵树相等和一棵树对称的情况，我们可以造一道题，判断两棵树是否对称的。如下就是一个对称的二叉树，那该如何写代码实现呢？请你思考。

2. 路径专题

关于二叉树有几道与路径有关的题目，我们一起看一下。

2.1 二叉树的所有路径

题目要求：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。 叶子节点是指没有子节点的节点。

示例：
输入：root = [1,2,3,null,5] 
输出： ["1->2->5","1->3"]

对于这个题，我们可以注意到右几个叶子节点，就有几条路径，那我们如何能找到叶子节点呢？深度优先、层次遍历是不是都可以？递归和迭代都可以？那组合一下自然就有很多种方式了，但是不同方法实现的难易程度不一样，我们这里只看深度优先搜索的方法。深度优先搜索就是从根节点开始，一直往左子节点走，直到左子节点为空，然后返回到上一步从右子节点在执行同样的操作，就像下面图中这样：

二叉树的深度优先搜索代码如下：

public static void treeDFS(TreeNode root) {
	//当前节点为空直接返回 if (root == null)
	return;
	//打印当前节点的值
	System.out.println(root.val); 
	//然后递归遍历左右子节点
	treeDFS(root.left);
	treeDFS(root.right);
}

我们完全可以仿照上面的代码来写，不同的是每个节点访问的时候不是把他打印出来，而是先把他存储起来，到叶子节点的时候再添加到集合中，最后返回集合的值 :

public List<String> binaryTreePaths(TreeNode root) {
	List<String> res = new ArrayList<>();
	dfs(root, "", res);
	return res;
}
private void dfs(TreeNode root, String path, List<String> res) {
	//如果为空，直接返回 
	if (root == null)
		return;
	//如果是叶子节点，说明找到了一条路径，把它加入到res中
	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);
}

2.2 路径总和

上面我们讨论的找所有路径的方法，那我们是否可以再找一下哪条路径的和为目标值呢？这就是112题。

给你二叉树的根节点 root 和一个表示目标和的整数targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。叶子节点是指没有子节点的节点。

示例1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 
输出：true