Symmetric Tree

• Easy
• keyword: Recursion, Top-down, Bottom-up
• 类似: Tree DFS, iteration

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

思考

• 最先想到的是in-order得到array, 然后像anagram那样双指针(注意到anagram和best meeting point类似, 可以从中间开始到两边, 但是两边往中间可以避免even/odd的区别)
• 但显然是很慢的.
• 那么怎么使用recursion的过程中比较呢? 我一开始的想法是: 因为对称就是对称的比较, 那么怎么对称的recursion呢?
  • 怎么对对称的node recursion?

idea 1: 对称的DFS

• 对每一个node recursion的话, 只能比较它自己subtree的内容, 但是这里要比较2对node的subtree, 很简单: recursion用2个param即可: left,right. 然后对称的recursion即可.
• 代码如下:

private boolean symmRec(TreeNode left, TreeNode right) {
    if (left == null && right == null)  return true;
    if (left == null || right == null)  return false;
    return left.val == right.val && symmRec(left.left, right.right) && symmRec(left.right, right.left);
}

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

idea 2: iteration : 这个我不熟悉, 九章说过Tree的iteration必背.

• discuss里面还说了iteration有2种: 一个是Queue, 一个是stack. 而且说Stack是O(lgN), queue是O(N). 参考Tree versions in Java: recursion, optimized tail recursion and pre-order iteration
• 这里参考的discuss的解答, 注意: stack的iteration并不是level order!!! 通过走一个例子就能发现stack loop的时候并不是level order的. 但是重点在于每一个node都检查即可.
• 代码如下:

public boolean isSymmetric(TreeNode root) {
    if (root == null)  return true;
    Stack<TreeNode> stk = new Stack<>();
    stk.push(root.left);
    stk.push(root.right);
    while (!stk.isEmpty()) {
        TreeNode node1 = stk.pop();
        TreeNode node2 = stk.pop();
        if (node1 == null && node2 == null)
            continue;
        if (node1 == null || node2 == null)
            return false;
        if (node1.val != node2.val)
            return false;
        stk.push(node1.left);
        stk.push(node2.right);
        stk.push(node1.right);
        stk.push(node2.left);
    }
    return true;
}