Symmetric Tree


Can we do it with DFS? I think it is the same as the second solution other than the fact that DFS uses stacks.
To be more specific, have two pointers(or stacks) traverse down left and right children. One will do postordertraversal on the left and the other will do preordertraversal.

There is another O(n) time O(1) space morris traversal algorithm
https://discuss.leetcode.com/topic/74692/3msciterativeontimeo1spacesolutionmorristraversal

Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.
https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

bool isSymmetric(TreeNode* root) { if(root == NULL){ return true; } queue<TreeNode*> lq; queue<TreeNode*> rq; if(root>left){ lq.push(root>left); } if(root>right){ rq.push(root>right); } while(lq.size() && rq.size()){ TreeNode *l = lq.front(); TreeNode *r = rq.front(); lq.pop(); rq.pop(); if(l>val != r>val) return false; if(l>left && r>right){ lq.push(l>left); rq.push(r>right); }else if(!l>left && !r>right){ }else{ return false; } if(l>right && r>left){ lq.push(l>right); rq.push(r>left); }else if(!l>right && !r>left){ }else{ return false; } } if(lq.size() != rq.size()){ return false; } return true; }

class Solution {
public boolean isSymmetric(TreeNode root) {
if (root==null) {
return true;
} else {
return isSymmetricInside(root.left, root.right);
}
}public boolean isSymmetricInside(TreeNode p, TreeNode q) { if (p==null && q==null) { return true; } if (p!=null && q!=null) { return p.val==q.val && isSymmetricInside(p.left, q.right) && isSymmetricInside(p.right, q.left); } return false; }
}

class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr)
{
return true;
}vector<int> leftTree; vector<int> rightTree; PreOrderTraversal(root>left, leftTree); ReversePreOrderTraversal(root>right, rightTree); int leftTreeSize = leftTree.size(); if (leftTreeSize != rightTree.size()) { return false; } for (int i = 0; i < leftTreeSize; ++i) { if (leftTree.at(i) != rightTree.at(i)) { return false; } } return true; } void PreOrderTraversal(TreeNode* node, vector<int>& vec) { if (node == nullptr) { vec.push_back(NULL); return; } vec.push_back(node>val); PreOrderTraversal(node>left, vec); PreOrderTraversal(node>right, vec); return; } void ReversePreOrderTraversal(TreeNode* node, vector<int>& vec) { if (node == nullptr) { vec.push_back(NULL); return; } vec.push_back(node>val); ReversePreOrderTraversal(node>right, vec); ReversePreOrderTraversal(node>left, vec); return; }
};