对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

image

解法一：

    我们知道中序遍历是先遍历左子节点，再遍历根节点，最后遍历右子节点。如果一颗二叉树是对称的，则使用中序遍历的对称遍历方法得到的结果应该与中序遍历的结果相同。所谓对称遍历方法，即先遍历右子节点，再遍历根节点，最后遍历左子节点。

    但是这种方法遇到第三种二叉树时，中序遍历结果为777777，中序遍历的对称遍历结果也为777777。要解决这个问题，只需要将空节点考虑进去就可以了。

public class Solution {
    ArrayList<TreeNode> preOrder = new ArrayList<TreeNode>();
    ArrayList<TreeNode> afterOrder = new ArrayList<TreeNode>();
    boolean isSymmetrical(TreeNode pRoot) {
        getPreOrder(pRoot);
        getAfterOrder(pRoot);
        //比较中序遍历和中序遍历的对称遍历
        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);
        }
    }
    //获得中序遍历的对称遍历
    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);
        }
    }
}

解法二：

在解法一中将全部的遍历序列进行了保存，之后再比较遍历序列。空间和时间效率都不是很好。可以在遍历二叉树的过程中进行比较，设置两个指针执行不同的遍历方法，比较两个指针的值。

下列代码使用了前序遍历和前序遍历的对称遍历。

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);
    }
}

解法三：

我们人工去分辨一棵树是否为对称二叉树时，不是使用各种遍历，而是直观地自上而下来判断每一行是否为对称的。于是我们也可以按层来遍历二叉树，再分析每一层是否对称。同样地，对于第三种二叉树的情况，需要考虑空节点。

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);
    }
        //按层判断是否对称
    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;
    }
}

由于每一层的数量不定，按层遍历时如果将所有的结果都放在一起，分析每一层是否对称时很难将每一层分开，于是我们采用ArrayList<ArrayList<TreeNode>>来存储每一层。