Time Complexity of Recursive Solution?


  • 0
    K

    Here is my AC code, I really eager to know the time complexity of this solution..
    I think it's O(n), since we do the (n/2) comparison at most. But I am not sure...

        public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;
            return dfs(root.left, root.right);
        }
        
        private boolean dfs(TreeNode left, TreeNode right) {
            if(left == null && right == null) return true;
            if(left == null || right == null) return false;
            if(left.right)
            /* Follow the symmetric defination */
            return (left.val == right.val) && dfs(left.right, right.left) && dfs(left.left, right.right);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.