20200807-200.same-tree.md

200.same-tree

题目链接：https://leetcode-cn.com/problems/same-tree/

题目

给定一组唯一的单词， 找出所有*不同* 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]] 
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]] 
解释: 可拼接成的回文串为 ["battab","tabbat"]

解题

思路[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)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  let queue1 = [p], queue2 = [q];
  while(queue1.length && queue2.length){
    let p_cache = queue1.shift()
    let q_cache = queue2.shift();
    if(p_cache === null && q_cache === null){
      continue;
    }
    if((p_cache && p_cache.val) !== (q_cache && q_cache.val)){
      return false;
    }
    queue1.push(p_cache.left)
    queue1.push(p_cache.right)
    queue2.push(q_cache.left)
    queue2.push(q_cache.right)
  }
  return true
};

/**
 * 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) {
  if(!p || !q) return p === q;
  if(p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

思考