【1对】Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

日期	是否一次通过	comment
2018-12-26 22:21	一次通过	sameTree的扩展
2018-12-27 14:24	看答案后通过	递归，理解不透；非递归，都为null时，漏掉continue
2019-01-13 16:06	一次通过	和sameTree共用一个模板

image.png

（来源： https://leetcode.com/problems/binary-tree-tilt/）

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        TreeNode node1 = root;
        TreeNode node2 = root;
        return dfs(node1, node2);
    }
    
    private boolean dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null) {
            return node1 == node2;
        }
        
        if(node1.val == node2.val) {
            return dfs(node1.left, node2.right) && dfs(node1.right, node2.left);
        }
        
        return false;
    }
}

递归改进版

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        
        return dfs(root.left, root.right);
    }
    
    private boolean dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null) {
            return node1 == node2;
        }
        
        if(node1.val != node2.val) {
            return false;
        }
        return dfs(node1.left, node2.right) && dfs(node1.right, node2.left);
    }
}

非递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        
        Stack<TreeNode[]> nodesS = new Stack<>();
        nodesS.push(new TreeNode[]{root.left, root.right});
        while(!nodesS.isEmpty()) {
            TreeNode[] treeNodes = nodesS.pop();
            if(treeNodes[0] == null || treeNodes[1] == null) {
                if(treeNodes[0] == null && treeNodes[1] == null) {
                    continue;
                }
                return false;
            }
            
            if(treeNodes[0].val != treeNodes[1].val) {
                return false;
            }
            nodesS.push(new TreeNode[]{treeNodes[0].left, treeNodes[1].right});
            nodesS.push(new TreeNode[]{treeNodes[0].right, treeNodes[1].left});
        }
        
        return true;
    }
}