数据结构入门之树

th3123.jpg

144. 二叉树的前序遍历

const preorderTraversal = (root) => {
  const res = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      res.push(root.val);
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    root = root.right;
  }
  return res;
}

94. 二叉树的中序遍历

var inorderTraversal = function (root) {
  if (!root) return [];
  const res = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root)
      root = root.left;
    }
    root = stack.pop();
    res.push(root.val);
    root = root.right;
  }
  return res;
};

145. 二叉树的后序遍历

var postorderTraversal = function (root) {
  const res = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      res.unshift(root.val);
      root = root.right;
    }
    root = stack.pop();
    root = root.left;
  }
  return res;
};

102. 二叉树的层序遍历

每次遍历一层的时候，把它的子节点依次按顺序保存 temp。把子节点的结果作为新的结果，也就是que = temp

let levelOrder = function(root) {
  let res = [], que = [root]
  if (!root) {
    return[]
  }
  while(que.length) {
    let temp = [], ans = []
    for (let i = 0; i < que.length; i++) {
      ans.push(que[i].val)
      if (que[i].left) {
        temp.push(que[i].left)
      }
      if (que[i].right) {
        temp.push(que[i].right)
      }
    }
    res.push(ans)
    que = temp
  }
  return res
}

104. 二叉树的最大深度

每一次用一个数组temp保存上一层的所有节点，每次计数器count+1。当temp为空的时候，也就是此时都是叶子节点情况。

let maxDepth = function(root) {
  if (!root) return 0
  let que = [root], res = 0
  while(que.length) {
    let temp = []
    for (let i = 0; i < que.length; i++) {
      if (que[i].left) {
        temp.push(que[i].left)
      }
      if (que[i].right) {
        temp.push(que[i].right)
      }
    }
    res += 1
    que = temp
  }
  return res
}

101. 对称二叉树

需要比较：

左右子树的根节点值是否相等

左右子树是否镜像对称

边界条件：

左右子树都为 null 时，返回 true

左右子树有一个 null 时，返回 false

let isSymmetric = function(root) {
  if (!root) {
    return true
  }
  let isEqual = function(left, right) {
    if (!left && !right){
      return true
    }
    if (!left || !right) {
      return false
    }

    return left.val === right.val && isEqual(left.left, right.right) && isEqual(left.right, right.left)
  }

  return isEqual(root.left, root.right)
}

226. 翻转二叉树

当节点为 null 的时候直接返回

如果当前结点不为null，那么先将其左右子树进行翻转，然后交换左右子树。

返回值为完成了翻转后的当前结点。

let invertTree = function(root) {
  if (root === null) {
    return root
  }

  let right = invertTree(root.right)
  let left = invertTree(root.left)

  root.left = right
  root.right = left
  return root
}

112. 路径总和

如果当前节点不是叶子节点，递归它的所有子节点，传递的参数就是 sum 减去当前的节点值；

如果当前节点是叶子节点，判断参数 sum 是否等于当前节点值，如果相等就返回 true，否则返回 false。

var hasPathSum = function(root, sum) {
    if (root === null) {
        return false
    }
    if (root.left === null && root.right === null) {
        return root.val === sum
    }
    sum = sum - root.val
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
};

700. 二叉搜索树中的搜索

根据二叉搜索树的特性，左子树全部都小于 root，右子树全部都大于 root

let searchBST = function(root, val) {
  if (root === null) {
    return null
  }
  if (root.val === val) {
    return root
  }

  return root.val < val ? searchBST(root.right, val) : searchBST(root.left, val)
}

701. 二叉搜索树中的插入操作

var insertIntoBST = function(root, val) {
    if (!root) {
        return new TreeNode(val)
    }
    if (root.val >= val) {
        root.left = insertIntoBST(root.left, val)
    }
    if (root.val < val) {
        root.right = insertIntoBST(root.right, val)
    }

    return root
};

98. 验证二叉搜索树

let isValidBST = function(root) {
  let dfs = function(root) {
    if (root === null) return true
    if (root.left) {
      if (root.left.val >= root.val) return false
      let rightest = getRightest(root.left)
      if (rightest && rightest.val >= root.val) return false
    }

    if (root.right) {
      if (root.right.val <= root.val) return false
      let leftest = getLeftest(root.right)
      if (leftest && leftest.val <= root.val) return false
    }

    return dfs(root.left) && dfs(root.right)
  }

  function getRightest(node) {
    while(node && node.right) node = node.right
    return node
  }

  function getLeftest(node) {
    while(node && node.left) node = node.left
    return node
  }

  return dfs(root)
}

653. 两数之和 IV - 输入 BST

var findTarget = function(root, k) {
    var findTargetFromHash = function(root, k, hash) {
        if (root === null) {
            return false
        }
        let remainder = k - root.val
        if (hash.hasOwnProperty(remainder)) {
            return true
        } else {
            hash[root.val] = true
        }
        return findTargetFromHash(root.left, k, hash) || findTargetFromHash(root.right, k, hash)
    }
    return findTargetFromHash(root, k, {})
};

235. 二叉搜索树的最近公共祖先

let lowestCommonAncestor = function(root, p, q) {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q)
  }
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q)
  }
  return root
}