Tuesday, January 31, 2017

Leetcode/各大家 -- 101. Symmetric Tree(Recur + Itera)


101. Symmetric Tree (Recursion + Iteration)


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

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

LinkedIn Bloomberg Microsoft



思路: use recursion to recursively find if nodes in left & right subtree match till leaves.
               helper(left.left ,right.right) && helper(left.right, right.left);

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return helper(root.left, root.right);
    }
    private boolean helper(TreeNode leftN, TreeNode rightN){
        if(leftN == null || rightN == null)
            return leftN == rightN;//need both be null
        if(leftN.val != rightN.val)
            return false;
        return helper(leftN.left, rightN.right) && helper(leftN.right, rightN.left);
    }
}



No comments:

Post a Comment