leetcode 待完善

一、树

1.判断是否是对称二叉树

// 前序遍历
var isSymmetric = function(root) {
    if (!root) {
        return true;
    }
    var Symmetric = function(p, q) {
        if (p == null && q != null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return Symmetric(p.left, q.right) && Symmetric(p.right, q.left);
    };
    return Symmetric(root.left, root.right);
};

2.序列化与反序列化二叉树

// 在重建二叉树时，当遇到特殊符号当空节点进行处理
var a = {
  val: 1,
  left: {val: 2},
  right: {val: 3, left: {val: 4}, right: {val: 5}}
}
function Serialize(pRoot,arr =[]){
if(!pRoot)

{  arr.push('#');} 
else
{
 arr.push(pRoot.val);
 Serialize(pRoot.left,arr);
 Serialize(pRoot.right,arr)
}   
return arr.join(',');
}
Serialize(a); //  1,2,#,#,3,4,#,#,5,#,#

function Deserialize(s)
 {
   if(!s){return null;}
   return deserialize(s.split(','));
}

function deserialize(arr)
{
  let node = null;
  const current = arr.shift();
  if(current !=='#')
    {
      node ={ val:current }

        node.left =deserialize(arr);

        node.right = deserialize(arr);
    
    }

      
return node;
}
Deserialize('1,2,#,#,3,4,#,#,5,#,#'); // 

反序列化结果

3.广度优先遍历二叉树(递归版)

var result = []
var queue = [nodes]
var bfs = function(count) {
  count = count || 0
  if(queue[count]) {
    result.push(queue[count].node)
    var left = queue[count].left
    var right = queue[count].right
    if(left) {
      queue.push(left)
    }
    if(right) {
      queue.push(right)
    }
    bfs(++count)
  }
}
bfs()
console.log(result)

4.入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

function FindPath(root, expectNumber){
  var temp = [];
  var result = [];
  dfs(root, 0);
  return result;
  function dfs(root, sum){
  if(!root){
      return;
    }
    temp.push(root.val);
    sum += root.val;
    if(!root.left && !root.right && sum === expectNumber){
      result.push(temp.concat());
    }
    if(root.left){
      dfs(root.left, sum);
    }
    if(root.right){
      dfs(root.right, sum);
    }
    temp.pop();
    return;
   }-

5.实现一个函数，传3个参数，指定数组（有小数、正负数），n（取出个数），sum（指定和），输出是否能找到这几个数。

这和经典的凑硬币问题其实本质上是相同的，可以用动态规划来做，但这里我们先考虑用深度搜索来做。

function findGroup(arr,n,sum){
    if(sum == 0 && n == 0){
        return true;
    }else if(n <= 0){
        return false;
    }
    if(n > 0)
        for(var i = 0; i < arr.length; i++){
            var temp = arr.slice(i+1,arr.length);
            return findGroup(temp,n-1,sum-arr[i]) || findGroup(temp,n,sum);
        }
}

二、排序

时间复杂度

三、查找

本身就是有顺序的可以考虑通过二分查找的方式来降低检索次数O( logn)