二叉树

平衡二叉树

var isBalanced = function (root) {
  if(!root) return true
  return Math.abs(depth(root.left) - depth(root.right)) <= 1
        && isBalanced(root.left)
        && isBalanced(root.right)
}
var depth = function (node) {
    if(!node) return -1
    return 1 + Math.max(depth(node.left), depth(node.right))
}

最近公共祖先节点

这里有点要注意的 dfs 传入的直接是 root.left 或者 root.right 这种就行, 这样有个好处就是不用在里面做一层判断了

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let ans;
    const dfs = (root, p, q) => {
        if (root === null) return false;
        const lson = dfs(root.left, p, q);
        const rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val === p.val || root.val === q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val === p.val || root.val === q.val);
    }
    dfs(root, p, q);
    return ans;
};

路径总和

求出有没有相关的target 值 有的话 返回 true

var hashPathSum = function(root, sum){
  if(!root) return false;
  let res = false;

  const dfs = (n, s)=>{
    if(!n.left && !.n.right && s===sum){
      res = true
    }
    if(n.left) dfs(n.left, s+ n.left.val)
    if(n.right) dfs(n.right, s+ n.right.val)
  }
  dfs(root, root.val)
  return res
}

路径总和

求所有路径的相加总和

var getPathSum = function(root){
  if(!root) return false;
  let num = 0;

  const dfs = (n, s)=> {
    if(!n.left && !n.right){
      num = num + s
    }
    num = s + n.value
    if(n.left) dfs(n.left, s + n.left)
    if(n.right) dfs(n.right, s + right)
  }

  dfs(root, root.value)
  return num
}

1. 二叉树的所有路径

var binaryTreePaths = function(root) {
    const paths = [];
    const construct_paths = (root, path) => {
        if (root) {
            path += root.val.toString();
            if (root.left === null && root.right === null) { // 当前节点是叶子节点
                paths.push(path); // 把路径加入到答案中
            } else {
                path += "->"; // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root.left, path);
                construct_paths(root.right, path);
            }
        }
    }
    construct_paths(root, "");
    return paths;
};

广度优先搜索

该方法是以横向的维度对dom树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点。

var BFS = function(node){
  const nodes = [];
  var i = 0;
  if(node){
    const queue = [];
    queue.unshift(node)
    while(queue.length != 0 ){
      var item = queue.shift();
      nodes.push(item.name);
      var children = item.children;
      for(var i = 0; i < children.length; i++){
        queue.push(chilren[i])
      }
    }
  }
  return nodes;
}

深度优先搜索

var DFS = function(node){
  var nodes = [];
  if(node != null){
    var stack = [];
    stack.push(node)
    while(stack.length != 0){
      var item = stack.pop();
      nodes.push(item);
      var children = item.children;
      for(var i = children.length -1; i >= 0; i--){
        stack.push(children[i])
      }
    }
  }
  return nodes
}

二叉树的最大深度和最小深度