101. Symmetric Tree (easy)

Q:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

A:

iterative 方法：   只需一层层地扫描，转换成一个类似于OJ's Binary Tree Serialization:的格式。 然后做对比即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return !root || isMirror(root->left, root->right);
    }
private:
    bool isMirror(TreeNode* l, TreeNode* r)
    {
        //BFS and check whether two list are reversely the same
        vector<TreeNode*> ll{l};
        vector<TreeNode*> lr{r};
        while(!ll.empty() && !lr.empty() && ll.size() == lr.size() )
        {
            vector<TreeNode*> nl, nr;
            for(int i =0;i<ll.size();++i)
            {
                TreeNode *tmp1 = ll[i];
                TreeNode* tmp2 = lr[i];
                if(!tmp1 && !tmp2)
                    continue;
                if(!tmp1 || !tmp2)
                    return false;
                if(tmp1->val != tmp2->val)
                    return false;
                // Now neither are NULL, add to next layer
                nl.push_back(tmp1->left);
                nl.push_back(tmp1->right);
                
                nr.push_back(tmp2->right);
                nr.push_back(tmp2->left);
            }
            ll = nl;
            lr = nr;
        }
        return ll.size() == lr.size();
    }
};

Mistakes:

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

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

这个是recursive 方法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return !root || isMirror(root->left, root->right);
    }
private:
    bool isMirror(TreeNode* left, TreeNode* right)
    {
        if( !left && !right)
            return true;
        if(!left || !right)
            return false;
        if (left->val != right->val)
            return false;
        return isMirror(left->left, right->right) && isMirror(left->right, right->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， 浪费时间， 完全就是在浪费时间！！！！！！！！！！！！！！！

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