Java One Recursive Solution and Two Iterative Solutions (DFS and BFS) With Explanations


  • 0
    L

    Solution 1: Recursive Solution

    // Method 1: Recursive Solution
    // Time: O(n)
    // Space: O(height)
    public boolean isSameTree(TreeNode p, TreeNode q) {
      // base cases
      if (p == null && q == null) {
        return true;
      } else if (p == null || q == null) {
        return false;
      } else if (p.val != q.val) {
        return false;
      }
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    

    Solution 2: Iterative DFS

    // Method 2: Iterative DFS
    // Time: O(n)
    // Space: O(height)
    public boolean isSameTree(TreeNode p, TreeNode q) {
      // Use Deque to help DFS
      Deque<TreeNode[]> stack = new LinkedList<>();
      stack.offerLast(new TreeNode[] {p, q});
      while (!stack.isEmpty()) {
        TreeNode[] cur = stack.pollLast();
        // Validate
        if (cur[0] == null && cur[1] == null) {
          continue;
        } else if (cur[0] == null || cur[1] == null) {
          return false;
        } else if (cur[0].val != cur[1].val) {
          return false;
        }
        // Offer children nodes
        stack.offerLast(new TreeNode[] {cur[0].left, cur[1].left});
        stack.offerLast(new TreeNode[] {cur[0].right, cur[1].right});
      }
      return true;
    }
    

    Solution 3: Iterative BFS

    // Method 3: Iterative BFS
    // Time: O(n)
    // Space: O(height)
    public boolean isSameTree(TreeNode p, TreeNode q) {
      // Use Deque to help DFS
      Queue<TreeNode[]> queue = new LinkedList<>();
      queue.offer(new TreeNode[] {p, q});
      while (!queue.isEmpty()) {
        TreeNode[] cur = queue.poll();
        // Validate
        if (cur[0] == null && cur[1] == null) {
          continue;
        } else if (cur[0] == null || cur[1] == null) {
          return false;
        } else if (cur[0].val != cur[1].val) {
          return false;
        }
        // Offer children nodes
        queue.offer(new TreeNode[] {cur[0].left, cur[1].left});
        queue.offer(new TreeNode[] {cur[0].right, cur[1].right});
      }
      return true;
    }
    

Log in to reply
 

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