101. Symmetric Tree (easy) ！！！！ 注意iterative方式

Q:

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

A:

iterative 方法：  

左右两边各自写成一个stack形式。然后一起比较

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root)
            return true;
        stack<TreeNode*> SL;
        SL.push(root->left); // save left,  remember to save nullptr
        stack<TreeNode*> SR;
        SR.push(root->right);
        while (!SL.empty()) {
            if (SR.empty())
                return false;
            auto l = SL.top();
            auto r = SR.top();
            SL.pop();
            SR.pop();
            if (!l && !r) {
                continue;
            } else if (!l || !r) {
                return false;
            } else {
                if (l->val != r->val) {
                    return false;
                }
                SL.push(l->left);
                SL.push(l->right);
                SR.push(r->right);
                SR.push(r->left);
            }
        }
        return SR.empty();
    }
};

Mistakes:

必须是右边的先加右子树，而不能是先左后又，然后倒着找。

--------------------------------------------------------------------------------

这个是recursive 方法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return helper(root->left, root->right);
    }
private:
    bool helper(TreeNode* rootL, TreeNode* rootR){
        if(rootL == nullptr && rootR == nullptr)
            return true;
        if(rootL == nullptr || rootR == nullptr)
            return false;
        return rootL->val == rootR->val && helper(rootL->left, rootR->right) && helper(rootL->right, rootR->left);
    }
};

------------------------------第二遍，     想只是给一个flag，标记先左还是先右，  这种最终证明，是不对的-------- 错误的关键问题在于， 题目本身只要求 对称， 就是对着中心一条轴对称即可。  那样左右扭来扭曲，就变得很奇怪的了。
---------但是，可以给出左右两个queue， 来对比每一层的结果，  也就是说，root的左边，一直先左子树。  root的右边，一直是先右子树。  ！！！-----------

public class Solution {
public boolean isSymmetric(TreeNode root) {
        // in-order tree traversal
        ArrayList<Integer> al = new ArrayList<Integer>();
        inOrder(root, al, true);
        int i = 0, j = al.size() - 1;
        while (i < j) {
            if (al.get(i++) != al.get(j--))
                return false;
        }
        return true;
    }

     void inOrder(TreeNode root, ArrayList<Integer> al, boolean leftFirst) {
        if (root == null)
            return;
        if (leftFirst) {
            if (root.left != null)
                inOrder(root.left, al, false);
            al.add(root.val);
            if (root.right != null)
                inOrder(root.right, al, false);
        } else {
            if (root.right != null)
                inOrder(root.right, al, true);
            al.add(root.val);
            if (root.left != null)
                inOrder(root.left, al, true);
        }
    }
}

哎， 以后过了12点，就不干活了。  TNND，  效率不行，还耽误睡觉。

好不容易搞出来了吧， 还TMD，净是在一些SB的小错误上浪费时间，没有意义啊。 干个啥呀？？？ Tiger
 以后状态不好的时候，不用coding， 浪费时间， 完全就是在浪费时间！！！！！！！！！！！！！！！

去玩儿吧， 去运动， 去看看小说，也行啊。  搞得心情不好，净在些拼写错误上啊，什么的浪费时间， 哎， ~~~~~~~~~~