101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
这个和之前的广度优先遍历二叉树很像：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) {
        return true;
    }
    var nowNodes = [root];
    var tamp,i,num,vals;
    while (nowNodes.length!==0) {
        tamp=[];
        vals=[];
        num = nowNodes.length;
        for (i = 0; i < num; i++) {
            if (nowNodes[i].left) {
                tamp.push(nowNodes[i].left);
                vals.push(nowNodes[i].left.val);
            } else {
                vals.push(null);
            }
            if (nowNodes[i].right) {
                tamp.push(nowNodes[i].right);
                vals.push(nowNodes[i].right.val);
            } else {
                vals.push(null);
            }
            
        }
        num = vals.length;
        for (i=0;i<num;i++) {
            if (vals[i]!==vals[num-1-i]) {
                return false;
            }
        }
        nowNodes = tamp;
        
    }
    return true;
};

教程给的标准方法使用了队列，这个方法和广度优先遍历二叉树比较像。

var q = [];
q.push(root);
q.push(root);
while (q.length!==0) {
    var t1 = q.shift();
    var t2 = q.shift();
    if (t1 === null && t2 === null) continue;
    if (t1 === null || t2 === null) return false;
    if (t1.val !== t2.val) return false;
    q.push(t1.left);
    q.push(t2.right);
    q.push(t1.right);
    q.push(t2.left);
}
return true;

这里在写一下二叉树的深度和广度遍历。
深度遍历用栈：

void DepthFirstTravel(Tree *root)  
{  
    stack<Tree *> s;  
    s.push(root);  
    while(!s.empty())  
    {  
        root = s.top();  
        cout << root->data << " ";  
        s.pop();  
        if(root->rchild != NULL)  
        {  
            s.push(root->rchild);  
        }  
        if(root->lchild != NULL)  
        {  
            s.push(root->lchild);  
        }  
  
    }  
}  

广度优先用队列：

void BreadthFirstTravel(Tree *root)  
{  
    queue<Tree *> q;  
    q.push(root);  
    while(!q.empty())  
    {  
        root = q.front();  
        cout << root->data << " ";  
        q.pop();  
        if(root->lchild != NULL)  
        {  
            q.push(root->lchild);  
        }  
        if(root->rchild != NULL)  
        {  
            q.push(root->rchild);  
        }  
    }  
}