对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
递归
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return helper(root.left,root.right);
}
public boolean helper(TreeNode root1,TreeNode root2){
if(root1==null&&root2==null){
return true;
}
if(root1==null||root2==null){
return false;
}
if(root1.val==root2.val){
return helper(root1.left,root2.right)&&helper(root1.right,root2.left);
}
return false;
}
迭代
使用栈或队列，两两一对访问
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root.left);
stack.push(root.right);
while (!stack.isEmpty()) {
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
if (node1 == null && node2 == null) {
continue;
}
if (node1 == null || node2 == null) {
return false;
}
if (node1.val != node2.val) {
return false;
}
stack.push(node1.left);
stack.push(node2.right);
stack.push(node1.right);
stack.push(node2.left);
}
return true;
}
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
递归
public boolean isSameTree(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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
迭代
public boolean isSameTree(TreeNode p, TreeNode q) {
Stack<TreeNode> stack = new Stack<>();
stack.push(p);
stack.push(q);
while (!stack.isEmpty()) {
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
if (node1 == null && node2 == null) {
continue;
}
if (node1 == null || node2 == null) {
return false;
}
if (node1.val != node2.val) {
return false;
}
stack.push(node1.left);
stack.push(node2.left);
stack.push(node1.right);
stack.push(node2.right);
}
return true;
}
另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
方一：两层递归
用主树的每一个节点做根与子树比较是否匹配
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return subRoot == null;
}
return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSameTree(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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
时间复杂度：对于每一个 s 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是 O(∣t∣)，那么总的时间代价就是 O(∣s∣×∣t∣)
方法二：转字符串比较
遍历两棵树得到字符串，注意需要将空节点算上
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
dfs(root, sb1);
dfs(subRoot, sb2);
return sb1.toString().indexOf(sb2.toString()) != -1;
}
private void dfs(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("#").append("null");
} else {
sb.append("#").append(root.val);
dfs(root.left, sb);
dfs(root.right, sb);
}
}
时间复杂度：遍历两棵树得到深度优先搜索序列的时间代价是)O(∣s∣+∣t∣)，在匹配的时候，如果使用暴力匹配，时间代价为 O(∣s∣×∣t∣)，使用 KMP 进行串匹配的时间代价都是O(∣s∣+∣t∣)
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
递归
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null || A == null) {
return false;
}
return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean dfs(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null) {
return false;
}
if (A.val != B.val) {
return false;
}
return dfs(A.left, B.left) && dfs(A.right, B.right);
}
迭代
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null || A == null) {
return false;
}
return helper(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean helper(TreeNode A, TreeNode B) {
Stack<TreeNode> stack = new Stack<>();
stack.push(A);
stack.push(B);
while (!stack.isEmpty()) {
TreeNode node2 = stack.pop();
TreeNode node1 = stack.pop();
if (node1 == null || node1.val != node2.val) {
return false;
}
// 相比于比较两棵树是否相等，加了if判断
if (node2.left != null) {
stack.push(node1.left);
stack.push(node2.left);
}
if (node2.right != null) {
stack.push(node1.right);
stack.push(node2.right);
}
}
return true;
}
合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则**不为 **NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
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;
}
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
迭代
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root1);
stack.add(root2);
while (!stack.isEmpty()) {
TreeNode node2 = stack.pop();
TreeNode node1 = stack.pop();
node1.val += node2.val;
// 如果两棵树的左子树不为空，将其左子树入栈
// 如果root1左子树为空，将root2的左子树作为root1的左子树
// 如果root2左子树为空，合并之后只有root1的左子树，即不做处理
if (node1.left != null && node2.left != null) {
stack.add(node1.left);
stack.add(node2.left);
} else if (node1.left == null) {
node1.left = node2.left;
}
if (node1.right != null && node2.right != null) {
stack.add(node1.right);
stack.add(node2.right);
} else if (node1.right == null) {
node1.right = node2.right;
}
}
return root1;
}
