題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)尘盼，用來判斷一顆二叉樹是不是對(duì)稱的统舀。注意，如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的澄港，定義其為對(duì)稱的椒涯。
解法一：
? ? 我們知道中序遍歷是先遍歷左子節(jié)點(diǎn)，再遍歷根節(jié)點(diǎn)回梧，最后遍歷右子節(jié)點(diǎn)废岂。如果一顆二叉樹是對(duì)稱的，則使用中序遍歷的對(duì)稱遍歷方法得到的結(jié)果應(yīng)該與中序遍歷的結(jié)果相同漂辐。所謂對(duì)稱遍歷方法泪喊，即先遍歷右子節(jié)點(diǎn)，再遍歷根節(jié)點(diǎn)髓涯，最后遍歷左子節(jié)點(diǎn)袒啼。
? ? 但是這種方法遇到第三種二叉樹時(shí)，中序遍歷結(jié)果為777777纬纪，中序遍歷的對(duì)稱遍歷結(jié)果也為777777蚓再。要解決這個(gè)問題，只需要將空節(jié)點(diǎn)考慮進(jìn)去就可以了包各。
public class Solution {
ArrayList<TreeNode> preOrder = new ArrayList<TreeNode>();
ArrayList<TreeNode> afterOrder = new ArrayList<TreeNode>();
boolean isSymmetrical(TreeNode pRoot) {
getPreOrder(pRoot);
getAfterOrder(pRoot);
//比較中序遍歷和中序遍歷的對(duì)稱遍歷
for(int i = 0; i < preOrder.size(); i++) {
if(preOrder.get(i) == null && afterOrder.get(i) != null) {
return false;
}
if(preOrder.get(i) != null && afterOrder.get(i) == null){
return false;
}
if(preOrder.get(i) == null && afterOrder.get(i) == null) {
continue;
}
if(preOrder.get(i).val != afterOrder.get(i).val) {
return false;
}
}
return true;
}
//獲得中序遍歷
public void getPreOrder(TreeNode pRoot) {
if(pRoot == null) {
preOrder.add(pRoot);
return ;
}
if(pRoot.left == null && pRoot.right == null) {
preOrder.add(pRoot);
}
else {
getPreOrder(pRoot.left);
preOrder.add(pRoot);
getPreOrder(pRoot.right);
}
}
//獲得中序遍歷的對(duì)稱遍歷
public void getAfterOrder(TreeNode pRoot) {
if(pRoot == null) {
afterOrder.add(pRoot);
return ;
}
if(pRoot.left == null && pRoot.right == null) {
afterOrder.add(pRoot);
}
else {
getAfterOrder(pRoot.right);
afterOrder.add(pRoot);
getAfterOrder(pRoot.left);
}
}
}
解法二：
在解法一中將全部的遍歷序列進(jìn)行了保存摘仅，之后再比較遍歷序列∥食空間和時(shí)間效率都不是很好娃属。可以在遍歷二叉樹的過程中進(jìn)行比較护姆，設(shè)置兩個(gè)指針執(zhí)行不同的遍歷方法矾端，比較兩個(gè)指針的值。
下列代碼使用了前序遍歷和前序遍歷的對(duì)稱遍歷卵皂。
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
return checker(pRoot, pRoot);
}
public boolean checker(TreeNode pRoot1, TreeNode pRoot2) {
if(pRoot1 == null && pRoot2 != null) {
return false;
}
if(pRoot1 != null && pRoot2 == null) {
return false;
}
if(pRoot1 == null && pRoot2 == null) {
return true;
}
if(pRoot1.val != pRoot2.val) {
return false;
}
return checker(pRoot1.left, pRoot2.right) && checker(pRoot1.right, pRoot2.left);
}
}
解法三：
我們?nèi)斯とシ直嬉豢脴涫欠駷閷?duì)稱二叉樹時(shí)秩铆，不是使用各種遍歷，而是直觀地自上而下來判斷每一行是否為對(duì)稱的灯变。于是我們也可以按層來遍歷二叉樹殴玛，再分析每一層是否對(duì)稱。同樣地添祸，對(duì)于第三種二叉樹的情況滚粟，需要考慮空節(jié)點(diǎn)。
public class Solution {
ArrayList<ArrayList<TreeNode>> list = new ArrayList<ArrayList<TreeNode>>();
boolean isSymmetrical(TreeNode pRoot) {
ArrayList<TreeNode> firstLine = new ArrayList<TreeNode>();
firstLine.add(pRoot);
list.add(firstLine);
if(pRoot == null) {
return true;
}
//按層遍歷二叉樹
for(int i = 0; i < list.size(); i++) {
ArrayList<TreeNode> currentLine = list.get(i);
ArrayList<TreeNode> newLine = new ArrayList<TreeNode>();
for(int j = 0; j < currentLine.size(); j++) {
TreeNode currentNode = currentLine.get(j);
if(currentNode != null && !(currentNode.left == null && currentNode.right == null)) {
newLine.add(currentNode.left);
newLine.add(currentNode.right);
}
}
if(newLine.size() != 0) {
list.add(newLine);
}
}
return check(list);
}
//按層判斷是否對(duì)稱
public boolean check(ArrayList<ArrayList<TreeNode>> list) {
for(int i = 0; i < list.size(); i++) {
ArrayList<TreeNode> currentLine = list.get(i);
int start = 0;
int end = currentLine.size() - 1;
while(start < end) {
if(currentLine.get(start) == null && currentLine.get(end) != null) {
return false;
}
if(currentLine.get(start) != null && currentLine.get(end) == null) {
return false;
}
if(currentLine.get(start) != null && currentLine.get(end) != null) {
if(currentLine.get(start).val != currentLine.get(end).val) {
return false;
}
}
start++;
end--;
}
}
return true;
}
}
由于每一層的數(shù)量不定刃泌，按層遍歷時(shí)如果將所有的結(jié)果都放在一起坦刀，分析每一層是否對(duì)稱時(shí)很難將每一層分開愧沟，于是我們采用ArrayList<ArrayList<TreeNode>>來存儲(chǔ)每一層。
