👨‍💻

Same Tree

https://leetcode.com/problems/same-tree/March 4, 2021

leetcode tree algorithm

On this page

Complete Data: 2020-12-21
Description
Example
Solution
Complexity Analysis

Complete Data: 2020-12-21

Description

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2,1], q = [1,1,2]
Output: false

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  const convertTreeToArray = (root) => {
    return root
      ? [
          root.val,
          convertTreeToArray(root.left),
          convertTreeToArray(root.right),
        ]
      : null;
  };

  return convertTreeToArray(p).join() === convertTreeToArray(q).join();
};

var isSameTree = function (p, q) {
  if(p==null && q ==null) return true

  if(p == null || q== null) return false

  if(p.val != q.val) return false

  return isSameTree(p.left，q.left) && isSameTree(p.right,q.right)
};

Complexity Analysis

Time complexity: O(N), where N is the number of nodes in the tree, since one visits each node exactly onece.
Space complexity: O(log(N)) in the best of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.

Edit this page