Symmetric Tree

https://leetcode.com/problems/symmetric-tree/description/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Thoughts

不难想到对每层检查是否是对称的。 需要注意的是要把null也考虑到。 还有就是dfs解法，同时追踪两个点，以root的左右两点为起始，可以观察到每次往下递归都要两个点相等且node1的左(右)和node2的右（左）相等。

Code

class Solution {

    public boolean isSymmetric(TreeNode root) {

        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int length = queue.size();
            TreeNode[] nodes = new TreeNode[length];
            for (int i = 0; i < length; i++) {
                TreeNode node = queue.remove();
                nodes[i] = node;
                if (node != null) {
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }

            for (int i = 0, j = length - 1; i < j; i++, j--) {         
                if (nodes[i] != null && nodes[j] != null && nodes[i].val != nodes[j].val ||
                    nodes[i] == null && nodes[i] != nodes[j] || nodes[j] == null && nodes[i] != nodes[j]) {
                    return false;
                }

            }

        }

        return true;
    }

}


public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmHelper(root.left, root.right);
    }

    private boolean isSymmHelper(TreeNode node1, TreeNode node2) {
        if (node1 == null) {
            return node2 == null? true: false;

        } else if (node2 == null) {
            return false;
        }

        if (node1.val != node2.val) {
            return false;
        }

        return isSymmHelper(node1.left, node2.right) &&
            isSymmHelper(node1.right, node2.left);
    }
}

Analysis

Errors: 1. nodes[i] == null && nodes[i] != nodes[j] 没有写nodes[i] == null

时间复杂度都是O(n)

Ver. 2

对两个树同时遍历，方向反着，检查是否同时想等。

/**
 * 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) {
        if (root == NULL) return true;
        stack<TreeNode*> l, r;
        if (root->left != NULL) l.push(root->left);
        if (root->right != NULL) r.push(root->right);
        while (!l.empty() && !r.empty()) {
            const auto l_cur = l.top(); l.pop();
            const auto r_cur = r.top(); r.pop();
            if (l_cur->val != r_cur->val) return false;
            if (l_cur->left != NULL) {
                if (r_cur->right == NULL) return false;
                l.push(l_cur->left);
                r.push(r_cur->right);
            }
            if (l_cur->right != NULL) {
                if (r_cur->left == NULL) return false;
                l.push(l_cur->right);
                r.push(r_cur->left);
            }
            if (r_cur->left != NULL && l_cur->right == NULL || r_cur->right != NULL && l_cur->left == NULL) return false;
        }
        if (!l.empty() || !r.empty()) return false;
        return true;
    }
};