LeetCode 战记 - 二叉树刷题笔记

LeetCode 战记 - 二叉树刷题笔记

知识点:

二叉树的三种遍历方式:

三种方式的「 序 」就是他们处理逻辑所在的位置。

  • 层序遍历:

    可以借助 队列 这样的数据结构。

    function traverse(root) {
      if (!root) return // 根结点即为空
    
    	let queue = [root]
      while (queue.length !== 0) {
        const node = queue.pop()
        // do something with node
        if (node.left) queue.unshift(node.left)
        if (node.right) queue.unshift(node.right)
    	}
    }
    
  • 前序遍历:

    function traverse(node) {
    	if (node !== null) {
        // do something with node
    	  traverse(node.left)
        traverse(node.right)
      }
    }
    
  • 中序遍历:

    function traverse(node) {
    	if (node !== null) {
    	  traverse(node.left)
        // do something with node
        traverse(node.right)
      }
    }
    
  • 后序遍历:

    function traverse(node) {
    	if (node !== null) {
    	  traverse(node.left)
        traverse(node.right)
        // do something with node
      }
    }
    

二叉树类的简单题基本上遵循「 写一个递归函数,构建起树或者对树做遍历 」的模版:

例如 LeetCode 108 - 2020.07.03 每日一题:

108. 将有序数组转换为二叉搜索树

难度:简单

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5
/**
 * Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    function build(l, r) {
        if (l > r) return null
        const mid = l + Math.floor((r - l) / 2)
        const root = new TreeNode(nums[mid])
        root.left = build(l, mid - 1)
        root.right = build(mid + 1, r)
        return root
    }

    return build(0, nums.length-1)
};

二叉树对于递归的考察比较多,再看 剑指Offer.28 对称的二叉树:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isSymmetric = function(root) {
  function check(l, r) {
    if (!l && !r) return true
    if (!l || !r) return false
    return l.val === r.val && check(l.left, r.right) && check(l.right, r.left)
  }
  
  return !root || check(root.left, root.right)
};

做递归思考三步:

  1. 递归的函数要干什么?

    • 函数的作用是判断传入的两个树是否镜像。
    • 输入:TreeNode 左节点、右节点
    • 输出:boolean
  2. 递归停止的条件是什么?

    • 左节点和右节点都为空: 倒底了都长得一样 ⇒ true
    • 左节点为空的时候右节点不为空,或反之: 长得不一样 ⇒ false
    • 左右节点值不相等: 长得不一样 ⇒ false
  3. 从某层到下一层的关系是什么?

    • 要想两棵树镜像,那么:一棵树左边的左边要和二棵树右边的右边镜像,一棵树左边的右边要和二棵树右边的左边镜像
    • 调用递归函数传入「左左」和「右右」
    • 调用递归函数传入「左右」和「右左」
    • 只有左左和右右镜像且左右和右左镜像的时候,我们才能说这两棵树是镜像的
  4. 调用递归函数,我们想知道它的左右子节点是否镜像,传入的值是 root 的左节点和右节点。

    这之前记得判断一下 root==null

再来一道面试真题:

LeetCode 112. 路经总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
  if (root == null) return false

  sum -= root.val
  if (!root.left && !root.right) { // 到了叶子节点
    return sum === 0
  }
  
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
};

剑指 Offer 55 - II. 平衡二叉树

难度:简单

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

  • 示例 1:

给定二叉树 [3,9,20,null,null,15,7],返回 true 

    3
   / \
  9  20
    /  \
   15   7
  • 示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4],返回 false 

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

  • 限制:1 <= 树的结点个数 <= 10000
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
  let result = true

  function getDepth(node) {
    if (node === null) return 0

    const left = getDepth(node.left)
    const right = getDepth(node.right)

    if (Math.abs(left - right) > 1) {
      result = false
    }  // 有隐患,其实可以优化,因为这里并没有实质性完成 “剪枝” 的动作

    return Math.max(left, right) + 1
  }

  getDepth(root)
  return result
};

1038. 从二叉搜索树到更大和树

难度:中等

给出二叉 搜索 树的根节点,该二叉树的节点值各不相同,修改二叉树,使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

提示:

  1. 树中的节点数介于 1 和 100 之间。
  2. 每个节点的值介于 0 和 100 之间。
  3. 给定的树为二叉搜索树。
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var bstToGst = function(root) {
  let sum = 0
  function latterTraverse(node) {
    if (node !== null) {
      latterTraverse(node.right)
      sum += node.val
      node.val = sum
      latterTraverse(node.left)
    }
  }

  latterTraverse(root)
  return root
};
  • 后序遍历:

    一些挺神经刀的歪题:

    剑指 Offer 33. 二叉搜索树的后序遍历序列

    难度:中等

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

    参考以下这颗二叉搜索树:

         5
        / \
       2   6
      / \
     1   3
    

    示例 1:

    输入: [1,6,3,2,5]
    输出: false
    

    示例 2:

    输入: [1,3,2,6,5]
    输出: true
    

    提示:数组长度 <= 1000

    辅助栈法:

    • 复杂度分析
      • 时间复杂度 $O(N)$ : 遍历 postorder 所有节点,各节点均入栈 / 出栈一次。
      • 空间复杂度 $O(N)$ : 最差情况下,单调栈存储所有节点,使用 $O(N)$ 额外空间。
    /**
     * @param {number[]} postorder
     * @return {boolean}
     */
    var verifyPostorder = function(postorder) {
      if (postorder.length < 2) return true
    
      let root = Number.POSITIVE_INFINITY
      let stack = []
      for (let i = postorder.length - 1; i >= 0; i--) {
        if (postorder[i] > root) return false
        while (stack.length && stack[stack.length - 1] > postorder[i]) {
                             // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                             // Q: 这一段为什么要循环出栈?
                             // A: 为了找到该子树的根节点
          root = stack.pop()
        }
        stack.push(postorder[i])
      }
      return true
    };
    

    剑指 Offer 07. 重建二叉树

    难度:中等

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    例如,给出

    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7
    

    限制:0 <= 节点个数 <= 5000

    思路:

    谨记知识点!前序遍历的顺序:根 - 左 - 右,而中序遍历的顺序是:左 - 根 - 右

    所以 preorder 中的第一个元素一定是根节点,我们要在中序结果 inorder 中找到它的位置,进而切片、划分出左右两个子树的前序、中序数组。

    本质上还是一个递归的思想。

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {number[]} preorder
     * @param {number[]} inorder
     * @return {TreeNode}
     */
    var buildTree = function(preorder, inorder) {
      if (!preorder.length && !inorder.length) return null;
    
      let root = new TreeNode(preorder[0]);
      const mid = inorder.findIndex((e) => e === root.val);
      let leftInorderChildren = inorder.slice(0, mid);
      let leftPreorderChildren = preorder.slice(1, 1 + leftInorderChildren.length);
      let rightInorderChildren = inorder.slice(mid + 1);
      let rightPreorderChildren = preorder.slice(1 + leftInorderChildren.length);
      root.left = buildTree(leftPreorderChildren, leftInorderChildren);
      root.right = buildTree(rightPreorderChildren, rightInorderChildren);
    
      return root;
    };
    

    剑指 Offer 54. 二叉搜索树的第k大节点

    难度:简单

    给定一棵二叉搜索树,请找出其中第 k 大的节点。

    示例 1:

    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 4
    

    示例 2:

    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 4
    

    限制:1 ≤ k ≤ 二叉搜索树元素个数

    思路:

    这里要用到一个性质:二叉搜索树的中序遍历为 递增序列 。

    那么只需要拿到中序遍历序列,翻转再取第 k - 1 即可。

    • 时间复杂度:$O(N)$
    • 空间复杂度:$O(N)$
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} k
     * @return {number}
     */
    var kthLargest = function(root, k) {
      let list = []
      function traverse(node) {
        if (!node) return
    
        traverse(node.left)
        list.push(node.val)
        traverse(node.right)
      }
    
      traverse(root)
      list = list.reverse()
      return list[k - 1]
    };
    

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×