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;