Tree versions in Java: recursion, optimized tail recursion and pre-order iteration
The most simple version is normal recursion:\n\n    public class Solution {\n    \tpublic boolean isSymmetric(TreeNode root) {\n    \t\treturn this.isMirror(roo
The most simple version is normal recursion:\n\n    public class Solution {\n    \tpublic boolean isSymmetric(TreeNode root) {\n    \t\treturn this.isMirror(root, root);\n    \t}\n    \n    \tprivate boolean isMirror(TreeNode t0, TreeNode t1) {\n\t\tif (t0 == null || t1 == null) {\n\t\t\treturn t0 == t1;\n\t\t}\n\t\treturn t0.val == t1.val\n\t\t\t\t&& this.isMirror(t0.left, t1.right)\n\t\t\t\t&& this.isMirror(t0.right, t1.left);\n    \t}\n    }\n\nAnd the last recursive call in method isMirror() above can be optimized to loop, this will reduce the actual recursive calls:\n\n    public class Solution {\n    \tpublic boolean isSymmetric(TreeNode root) {\n    \t\treturn this.isMirror(root, root);\n    \t}\n    \n    \tprivate boolean isMirror(TreeNode t0, TreeNode t1) {\n    \t\twhile (t0 != null && t1 != null) {\n    \t\t\tif (t0.val != t1.val || !this.isMirror(t0.left, t1.right)) {\n    \t\t\t\treturn false;\n    \t\t\t}\n    \t\t\tt0 = t0.right;\n    \t\t\tt1 = t1.left;\n    \t\t}\n    \t\treturn t0 == t1;\n    \t}\n    }\nThere are two kinds of iteration at least. The BFS-like iteration, which is based on queue, has a space complexity of O(n). And the DFS-like iteration, which is based on stack, has a better space complexity of O(log n).\n\nHere is the DFS-like pre-order iteration:\n\n    public class Solution {\n    \tpublic boolean isSymmetric(TreeNode root) {\n    \t\tDeque<TreeNode[]> stack = new LinkedList<>();\n    \t\tstack.push(new TreeNode[]{root, root});\n    \t\twhile (!stack.isEmpty()) {\n    \t\t\tTreeNode[] pair = stack.pop();\n    \t\t\tTreeNode t0 = pair[0], t1 = pair[1];\n    \t\t\tif (t0 == null && t1 == null) {\n    \t\t\t\tcontinue;\n    \t\t\t}\n    \t\t\tif (t0 == null || t1 == null || t0.val != t1.val) {\n    \t\t\t\treturn false;\n    \t\t\t}\n    \t\t\tstack.push(new TreeNode[]{t0.left, t1.right});\n    \t\t\tstack.push(new TreeNode[]{t0.right, t1.left});\n    \t\t}\n    \t\treturn true;\n    \t}\n    }
[]