给定两二叉树，判断该两树是否对称？

如下图即为两树对称：

图1.png

对于树的遍历，一般想到的解法有两种，递归或者使用非递归的解法。
对于该题而言，无论是哪种解法，每执行一步，均要判断该树的节点是否和对应数的反方向节点是否一致，如果不一致直接返回false，否则继续执行下一步。

一，递归解法

private static boolean isSymmetricTree(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null && node2 != null) return false;
        if (node1 != null && node2 == null) return false;
        if (node1.value != node2.value) return false;
        return isSymmetricTree(node1.left, node2.right) && isSymmetricTree(node1.right, node2.left);
    }

二，非递归解法

1，O(n)空间复杂度的解法

一般的，常规非递归解法，需要引入额外空间集合用于存放当前临时变量，不断遍历该集合直至为空，执行结束。
对于该题而言，由于是两棵树，一棵是先根遍历，另外一棵就对应反向先根遍历，即先右，再根，再左的顺序。如何保证每次循环都保证是指定索引节点的判断，而且保证对应数的遍历顺序呢？由于每次都是1对的比较，则每次比较前集合均只应该存一对数据，即可用的数据结构可以是队列，也可以是堆栈。如下以队列举例：

图2.png

// 非递归O(n)空间复杂度的解法
private static boolean isSymmetricTyeeByDeque(TreeNode root1, TreeNode root2) {
    LinkedList<TreeNode> list = new LinkedList<>();
    list.add(root1);
    list.add(root2);
    while(!list.isEmpty()) {
        TreeNode node1 = list.pop();
        TreeNode node2 = list.pop();
        // null判断主要是用于root的判断
        if (node1 == null && node2 == null) return true;
        if (node1 == null && node2 != null) return false;
        if (node1 != null && node2 == null) return false;
        if (node1.value != node2.value) return false;
            
        if(node1.left != null) {                
            list.add(node1.left);
        }
        if (node2.right != null) {              
            list.add(node2.right);
        }
            
        if (node1.right != null) {
            list.add(node1.right);
        }
        if (node2.left != null) {
            list.add(node2.left);
        }
    }
    return true;
}

2，O(1)空间复杂度的解法

如何才能保证在不引入其他额外空间的情况下判断两树是否对称？这里我首先想到的就是Morris算法了。其思想就是，每次遍历，便查找当前节点是否有前驱节点，并且前驱节点是否指向了自己，如果没有指向自己，便指向自己，并且指针左子树下移，否则断开前驱节点与自己的联系，指针下移到右子树，以达到遍历整棵树的目的。还是画一个及其简单的效果图吧...

Morris效果图.png

// O(1)空间复杂度解法
private static boolean isSymmetricByMorris(TreeNode root1, TreeNode root2) {
    TreeNode cur1 = root1;
    TreeNode cur2 = root2;
    while(cur1 != null || cur2 != null) {
        if (cur1 == null && cur2 == null) return true;
        if (cur1 == null && cur2 != null) return false;
        if (cur1 != null && cur2 == null) return false;
        if (cur1.value != cur2.value) return false;
            
        // 获取左子树下一节点，cur获取方向从左至右
        if (cur1.left != null) {
            TreeNode symmPreNode = getSymmPreNode(cur1);
            if (symmPreNode.right != cur1) {                    
                symmPreNode.right = cur1;
                cur1 = cur1.left;
            } else {
                symmPreNode.right = null;
                cur1 = cur1.right;
            }
        } else {
            cur1 = cur1.right;
        }
        if (cur1 != null) {             
            System.out.println(cur1.value);
        }
            
        // 获取右子树下一节点，，cur获取方向从右至左
        if (cur2.right != null) {
            TreeNode symmNextNode = getSymmNextNode(cur2);
            if (symmNextNode.left == cur2) {
                symmNextNode.left = null;
                cur2 = cur2.left;
            } else {
                symmNextNode.left = cur2;
                cur2 = cur2.right;
            }
        } else {
            cur2 = cur2.left;
        }
        if (cur2 != null) {
            System.out.println(cur2.value);
        }
        System.out.println("----------------------");
    }
    return true;
}
    
// 获取当前节点的前驱节点，由于该方法之外已判断node不为null，故这里不用再做判断
private static TreeNode getSymmPreNode(TreeNode node) {
    TreeNode tn = node.left;
    while(tn.right != null && tn.right != node) {
        tn = tn.right;
    }
    return tn;
}

下面再给出当前我的测试用例

public class TreeNode {

    public int value;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public static void main(String[] args) {
    TreeNode node16 = new TreeNode(16);
    TreeNode node18 = new TreeNode(18);
    TreeNode node19 = new TreeNode(19, node18, null);
    TreeNode node17 = new TreeNode(17);
    TreeNode node23 = new TreeNode(23);
    TreeNode node22 = new TreeNode(22, node17, node23);
    TreeNode node21 = new TreeNode(21, node16, node19);
    TreeNode node20 = new TreeNode(20, node21, node22);
        
    TreeNode node16$ = new TreeNode(16);
    TreeNode node18$ = new TreeNode(18);
    TreeNode node19$ = new TreeNode(19, null, node18$);
    TreeNode node17$ = new TreeNode(17);
    TreeNode node23$ = new TreeNode(23);
    TreeNode node22$ = new TreeNode(22, node23$, node17$);
    TreeNode node21$ = new TreeNode(21, node19$, node16$);
    TreeNode node20$ = new TreeNode(20, node22$, node21$);

    //  System.out.println(isSymmetricTree(node20, node20$));
    //  System.out.println(isSymmetricTyeeByDeque(node20, node20$));
    System.out.println(isSymmetricByMorris(node20, node20$));
    }

平时在练习过程中，随着练习的增多，代码也随之增大，删之可惜，本文所写纯粹是为记录点滴的需要，如有雷同纯属巧合。