简单

94.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：
image.png

  1. 输入：root = [1,null,2,3]
  2. 输出：[1,3,2]

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [1]
  2. 输出：[1]

示例 4：
image.png

  1. 输入：root = [1,2]
  2. 输出：[2,1]

示例 5：
image.png

  1. 输入：root = [1,null,2]
  2. 输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解：

递归

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. var inorderTraversal = function(root, arr = []) {
  6.     if (root) {
  7.         inorderTraversal(root.left, arr);
  8.         arr.push(root.val);
  9.         inorderTraversal(root.right, arr);
  10.     }
  11.     return arr;
  12. };

复杂度分析

  • 时间复杂度：O(n)，其中 nn 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
  • 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。

    迭代

    1. var inorderTraversal = function(root) {
    2.   let result = [];
    3.   let stack = [];
    4.   while (root || stack.length > 0) {
    5.       while (root) {
    6.           stack.push(root);
    7.           root = root.left;
    8.       }
    9.       root = stack.pop();
    10.       result.push(root.val);
    11.       root = root.right;
    12.   }
    13.   return result;
    14. };

    100.相同的树

    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
image.png

  1. 输入：p = [1,2,3], q = [1,2,3]
  2. 输出：true

示例 2：
image.png

  1. 输入：p = [1,2], q = [1,null,2]
  2. 输出：false

示例 3：
image.png

  1. 输入：p = [1,2,1], q = [1,1,2]
  2. 输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

题解：

递归

  1. /**
  2.  * @param {TreeNode} p
  3.  * @param {TreeNode} q
  4.  * @return {boolean}
  5.  */
  6. var isSameTree = function(p, q) {
  7.     // 如果p和q都是null，空二叉树，那么它们相等
  8.     if (p == null && q == null) {
  9.         return true;
  10.     }
  11.     if (p == null || q == null) {
  12.         return false;
  13.     }
  14.     if (p.val !== q.val) {
  15.         return false;
  16.     }
  17.     // p和q的值相同，需要递归遍历左右子树
  18.     return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  19. };

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长最路上的节点数。
说明：叶子节点是指没有子节点的节点。

示例 ：
给定二叉树 [3,9,20,null,null,15,7]，

  1.         3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最大深度为3。

题解：

递归

  1. var maxDepth = function(root) {
  2.     if (!root) {
  3.     return 0;
  4.   } else {
  5.     const left = maxDepth(root.left);
  6.     const right = maxDepth(root.right);
  7.     return Math.max(left, right) + 1;
  8.   }
  9. };

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
  • 空间复杂度：O(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

    144.二叉树的前序遍历

    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：
image.png

  1. 输入：root = [1,null,2,3]
  2. 输出：[1,2,3]

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [1]
  2. 输出：[1]

示例 4：
image.png

  1. 输入：root = [1,2]
  2. 输出：[1,2]

示例 5：
image.png

  1. 输入：root = [1,null,2]
  2. 输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

题解：

递归

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. var preorderTraversal = function(root, array = []) {
  6.     if (root) {
  7.           // 先处理自己，再处理左右
  8.         array.push(root.val);
  9.         preorderTraversal(root.left, array);
  10.         preorderTraversal(root.right, array);
  11.     }
  12.     return array;
  13. };

迭代

  1. var preorderTraversal = function(root) {
  2.     // 开始遍历，有一个stack存储
  3.     // left入栈 直到left为空
  4.     // 节点出栈 右孩子为目标
  5.     let result = [];
  6.     let stack = [];
  7.     while (root || stack.length) {
  8.         while (root) {
  9.             result.push(root.val);
  10.             stack.push(root); // 后面要通过curr找它的right
  11.             root = root.left;
  12.         }
  13.         root = stack.pop();
  14.         root = root.right;
  15.     }
  16.     return result;
  17. };

145.二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：
image.png

  1. 输入：root = [1,null,2,3]
  2. 输出：[3,2,1]

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [1]
  2. 输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

题解：

递归

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. var postorderTraversal = function(root, arr = []) {
  6.     if (root) {
  7.         postorderTraversal(root.left, arr);
  8.         postorderTraversal(root.right, arr);
  9.         arr.push(root.val);
  10.     }
  11.     return arr;
  12. };

226.反转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
image.png

  1. 输入：root = [4,2,7,1,3,6,9]
  2. 输出：[4,7,2,9,6,3,1]

示例 2：
image.png

  1. 输入：root = [2,1,3]
  2. 输出：[2,3,1]

示例 3：

  1. 输入：root = []
  2. 输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

题解：

递归

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {TreeNode}
  4.  */
  5. var invertTree = function(root) {
  6.     // 递归
  7.     // 终止条件
  8.     if (root == null) {
  9.         return root;
  10.     }
  11.     // 递归的逻辑
  12.     [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  13.     return root;
  14. };

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
image.png
示例 1:

  1. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
  2. 输出: 6 
  3. 解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

  1. 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
  2. 输出: 2
  3. 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

题解：

递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {TreeNode} p
  12.  * @param {TreeNode} q
  13.  * @return {TreeNode}
  14.  */
  15. var lowestCommonAncestor = function(root, p, q) {
  16.     if (p.val > root.val && q.val > root.val) {
  17.         return lowestCommonAncestor(root.right, p, q);
  18.     } else if (p.val < root.val && q.val < root.val) {
  19.         return lowestCommonAncestor(root.left, p, q);
  20.     } else {
  21.         return root;
  22.     }
  23. };

迭代

  1. var lowestCommonAncestor = function(root, p, q) {
  2.     while (root) {
  3.         if (p.val > root.val && q.val > root.val) {
  4.             root = root.right;
  5.         } else if (p.val < root.val && q.val < root.val) {
  6.             root = root.left;
  7.         } else {
  8.             return root;
  9.         }
  10.     }
  11. };

中等

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
image.png

  1. 输入：root = [2,1,3]
  2. 输出：true

示例 2：
image.png

  1. 输入：root = [5,1,4,null,null,3,6]
  2. 输出：false
  3. 解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

题解：

递归

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {boolean}
  4.  */
  5. var isValidBST = function(root) {
  6.     return helper(root, -Infinity, Infinity);
  7. };
  9. const helper = function(root, lower, upper) {
  10.     if (root === null) {
  11.       return true;
  12.   }
  13.   if (root.val <= lower || root.val >= upper) {
  14.       return false;
  15.   }
  16.   return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
  17. }

复杂度分析

  • 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

  • 空间复杂度 : O(n)，其中 nn 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。

    中序

    1. var isValidBST = function(root) {
    2.   let stack = [];
    3. let inorder = -Infinity;
    4. while (stack.length || root !== null) {
    5.     while (root !== null) {
    6.       stack.push(root);
    7.     root = root.left;
    8.   }
    9.   root = stack.pop();
    10.   // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
    11.   if (root.val <= inorder) {
    12.       return false;
    13.   }
    14.   inorder = root.val;
    15.   root = root.right;
    16. }
    17. return true;
    18. }

    复杂度分析

  • 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

  • 空间复杂度 : O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间。

    236.二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
image.png

  1. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  2. 输出：3
  3. 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
image.png

  1. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  2. 输出：5
  3. 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

  1. 输入：root = [1,2], p = 1, q = 2
  2. 输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

题解：

递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root
  10.  * @param {TreeNode} p
  11.  * @param {TreeNode} q
  12.  * @return {TreeNode}
  13.  */
  14. var lowestCommonAncestor = function(root, p, q) {
  15.     // 如果左边没有p或者q，那就去右边找
  16.     // 如果两边都找到了，那就是root
  17.     if (root == null || root == p || root == q) {
  18.         return root;
  19.     }
  20.     const left = lowestCommonAncestor(root.left, p, q);
  21.     const right = lowestCommonAncestor(root.right, p, q);
  22.     if (left == null) {
  23.         return right;
  24.     }
  25.     if (right == null) {
  26.         return left;
  27.     }
  28.     // 左右都找到了p或者q，那就是root了
  29.     return root;
  30. };