LeetCode Js-100. Same Tree

    AllenLi
    LeetCode Js-Binary Tree

    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.

    給與兩個二元樹分別為 p 和 q 的根，寫一個函式來檢查它們是否相同。
如果兩個二叉樹結構相同並且節點具有相同的值，則認為它們是相同的。

    Example 1:

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

    Example 2:

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

    Example 3:

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

    solution:
    1. 建立 recursion 的遞迴函式。
    2. 如果兩個 node 皆為 null，則為 true。
    3. 如果兩個 node 其中一個為 null，則為 false。
    4. 如果兩個 node 數值不同，則為 false。
    5. 運用遞迴函式來執行左右子樹的各自比較。

    Code 1:

    /**
 * 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)
 * }
 */
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

var isSameTree = function(p, q) {
    return recursion(p, q)
};

var recursion = function (p, q) {
    //如果兩個 node 皆為 null，則為 true。
    if (!p && !q) return true;
    //如果兩個 node 其中一個為 null，則為 false。
    if (!p || !q) return false;
    //如果兩個 node 數值不同，則為 false。
    if (p.val !== q.val) return false;

    //運用遞迴函式來執行左右子樹的各自比較。
    return recursion(p.left, q.left) && recursion(p.right, q.right);
}

    FlowChart:
    Example 1

    TreeNode {
  val: 1,
  left: TreeNode { val: 2, left: null, right: null },
  right: TreeNode { val: 3, left: null, right: null }
}
TreeNode {
  val: 1,
  left: TreeNode { val: 2, left: null, right: null },
  right: TreeNode { val: 3, left: null, right: null }
}
return true;

    Example 2

    TreeNode {
  val: 1,
  left: TreeNode { val: 2, left: null, right: null },
  right: null
}
TreeNode {
  val: 1,
  left: TreeNode {
    val: null,
    left: TreeNode { val: 2, left: null, right: null },
    right: null
  },
  right: null
}
return false;

    Example 3

    TreeNode {
  val: 1,
  left: TreeNode { val: 2, left: null, right: null },
  right: TreeNode { val: 1, left: null, right: null }
}
TreeNode {
  val: 1,
  left: TreeNode { val: 1, left: null, right: null },
  right: TreeNode { val: 2, left: null, right: null }
}
return false;

    Related Posts