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. 二叉樹的層序遍歷

每次遍歷一層的時候，把它的子節(jié)點依次按順序保存 temp。把子節(jié)點的結(jié)果作為新的結(jié)果，也就是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. 二叉樹的最大深度

每一次用一個數(shù)組temp保存上一層的所有節(jié)點，每次計數(shù)器count+1。當(dāng)temp為空的時候，也就是此時都是葉子節(jié)點情況。

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. 對稱二叉樹

需要比較：

左右子樹的根節(jié)點值是否相等

左右子樹是否鏡像對稱

邊界條件：

左右子樹都為 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. 翻轉(zhuǎn)二叉樹

當(dāng)節(jié)點為 null 的時候直接返回

如果當(dāng)前結(jié)點不為null，那么先將其左右子樹進(jìn)行翻轉(zhuǎn)，然后交換左右子樹。

返回值為完成了翻轉(zhuǎn)后的當(dāng)前結(jié)點。

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. 路徑總和

如果當(dāng)前節(jié)點不是葉子節(jié)點，遞歸它的所有子節(jié)點，傳遞的參數(shù)就是 sum 減去當(dāng)前的節(jié)點值；

如果當(dāng)前節(jié)點是葉子節(jié)點，判斷參數(shù) sum 是否等于當(dāng)前節(jié)點值，如果相等就返回 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. 二叉搜索樹中的搜索

根據(jù)二叉搜索樹的特性，左子樹全部都小于 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. 兩數(shù)之和 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
}