相同的樹
思路一：序列化
將兩棵樹進(jìn)行序列化，然后比較序列化后的字符串即可，相同返回true,不同返回false;
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
String pStr = serializeTreeByPreOrder(p);
String qStr = serializeTreeByPreOrder(q);
return pStr.equals(qStr);
}
private static String serializeTreeByPreOrder(TreeNode root){
if(root == null){
return "#_";
}
String res = root.val + "_";
res += serializeTreeByPreOrder(root.left);
res += serializeTreeByPreOrder(root.right);
return res;
}
}
時(shí)間復(fù)雜度：因?yàn)樾蛄谢僮餍枰闅v二叉樹歼狼，所以時(shí)間復(fù)雜度為O(N)
額外空間復(fù)雜度：使用了字符串去保存序列化的二叉樹每個(gè)節(jié)點(diǎn)值，額外空間復(fù)雜度為O(N)
執(zhí)行結(jié)果：
思路二：recursion
遞歸的思路如下：
- 判斷兩個(gè)指針當(dāng)前節(jié)點(diǎn)值是否相等
- 判斷 A 的左子樹與 B 的左子樹是否相等
- 判斷 A 的右子樹與 B 的右子樹是否相等
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
return (p.val == q.val)
&& isSameTree(p.left,q.left)
&& isSameTree(p.right,q.right);
}
}
時(shí)間復(fù)雜度：O(N)
額外空間復(fù)雜度：最大的遞歸深度是當(dāng)二叉樹退化為線性鏈表的時(shí)候，額外空間復(fù)雜度為O(N)
執(zhí)行結(jié)果：
對稱二叉樹
思路一：序列化
對于一棵對稱的二叉樹：
1
/ \
2 2
/ \ / \
3 4 4 3
它的先序遍歷的結(jié)果為：1,2,3,4,2,4,3
先序遍歷的順序?yàn)?node->node.left->node.right;
如果遍歷的順序?yàn)?node->node.right->node.left;
那么這種方式遍歷的結(jié)果為：1,2,3,4,2,4,3 同先序遍歷結(jié)果一致
所以嚎朽，可以用二叉樹序列化的思想，使用先序和類似于后序遍歷的思路將樹序列化之后進(jìn)行比對柬帕，結(jié)果相同則說明樹是對稱的哟忍。
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
String res1 = serializeTreeByPreOrder(root);
String res2 = serializeTreeByPosOrder(root);
return res1.equals(res2);
}
private static String serializeTreeByPreOrder(TreeNode root){
if(root == null){
return "#_";
}
String res = root.val + "_";
res += serializeTreeByPreOrder(root.left);
res += serializeTreeByPreOrder(root.right);
return res;
}
private static String serializeTreeByPosOrder(TreeNode root){
if(root == null){
return "#_";
}
String res = root.val + "_";
res += serializeTreeByPosOrder(root.right);
res += serializeTreeByPosOrder(root.left);
return res;
}
}
該算法的時(shí)間復(fù)雜度為：O(N)；因?yàn)閷Χ鏄湫蛄谢枰闅v每一個(gè)節(jié)點(diǎn)
額外空間復(fù)雜度為：O(N)陷寝；額外使用了字符串保存二叉樹的所有節(jié)點(diǎn)的值
執(zhí)行結(jié)果：
思路二： recursion
遞歸思路：
- 判斷兩個(gè)指針當(dāng)前節(jié)點(diǎn)值是否相等
- 判斷 A 的右子樹與 B 的左子樹是否對稱
- 判斷 A 的左子樹與 B 的右子樹是否對稱
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root,root);
}
private boolean isMirror(TreeNode root1,TreeNode root2){
if(root1 == null && root2 == null){
return true;
}
if(root1 == null || root2 == null){
return false;
}
return (root1.val == root2.val)
&& (isMirror(root1.left,root2.right))
&& (isMirror(root1.right,root2.left));
}
}
時(shí)間復(fù)雜度:O(N)
額外空間復(fù)雜度:當(dāng)二叉樹退化為線性的鏈表時(shí)锅很，額外空間復(fù)雜度為O(N)
執(zhí)行結(jié)果：
