leetcode-tree习题

2020-01-26 by 杜宏伟

树是一种常数据结构,需要熟悉对树的各种操作。

先序:考察到一个节点后,即刻输出该节点的值,并继续遍历其左右子树。(根左右)

中序:考察到一个节点后,将其暂存,遍历完左子树后,再输出该节点的值,然后遍历右子树。(左根右)

后序:考察到一个节点后,将其暂存,遍历完左右子树后,再输出该节点的值。(左右根)

二叉搜索树(Binary Search Tree)是指一棵空树或具有如下性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 任意节点的左、右子树也分别为二叉搜索树
  4. 没有键值相等的节点

二叉树中的遍历

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * 中序遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let result = []
  if(!root) return []
  function helper(root) { 
    if (!root) { 
      return
    }
    //result.push(root.val),放这就是前序遍历
    helper(root.left)
    result.push(root.val)
    helper(root.right)
    //放这就是后序遍历
    result.push(root.val)
  }
  helper(root)
  return result
};

位置以root为谁。比如 中序就是先输出左,再输出root,也就是中,再输出右。

非递归的写法

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

对称二叉树

把一棵树,当作两棵树,分别对左右,右左子树做比对。

给定一个二叉树,检查它是否是镜像对称的。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {

  function helper(root1, root2) {
    if (root1 === null && root2 == null) return true
    if (!root1 || !root2) { return false }

    if (root1.val != root2.val) return false

    return helper(root1.left, root2.right) && helper(root1.right, root2.left)

  }
  return helper(root, root)
};

二叉树的层次遍历

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

可以用深度优先和广度优先做法。下面用深度优先举例。

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  let result = []
  function helper(root, level) {
    if (!root) return 
    if (!result[level]) {
      result[level] = []
    }
    result[level].push(root.val)
    helper(root.left, level + 1)
    helper(root.right, level + 1)
  }
  helper(root, 0)
  return result
};

二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

和上题相同,只是加一个level是奇偶的判断。

if (level % 2) {
  result[level].unshift(root.val)

}
else {
  result[level].push(root.val)
}

二叉树的最大深度

相于当是动态规划的思想,从最深处开始算是0(null算是0),然后一点点加起来。

var maxDepth = function (root) {
  if (!root) return 0

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

从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7
前序遍历是 中左右
中序遍历是 左中右

中左做一组考虑,通过中节点,可以把数组分成两部分。 通过rootIndex把数据分成左右子树

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if(!preorder.length) return null
  let nodeVal = preorder[0]
  let rootIndex = inorder.indexOf(nodeVal)
  let node = new TreeNode(nodeVal)
  node.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex))
  node.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1))
  return node
};

从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

和上面的一样,只是slice时索引不大一相,左做为一组,还是以nodeIndex做为分界

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  if (!inorder.length) return null
  let nodeVal = postorder[postorder.length - 1]
  let rootIndex = inorder.indexOf(nodeVal)
  let node = new TreeNode(nodeVal)
  node.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex))
  node.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex, postorder.length - 1))
  return node
};

不同的二叉搜索树 II

给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。

从1..n依次选择一个数做为根节点,找出左面的组合总数,右面的组合总数,左右相互匹配得到所有组合

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n <= 0) {
    return []
  }
  function helper(m, n) {
    if (m == n) {
      return [new TreeNode(m)]
    }
    if (m > n) {
      return [null]
    }
    let result = []
    for (let i = m; i <= n; i++) {
      let left = helper(m, i - 1)
      let right = helper(i + 1, n)

      for (itemLeft of left) {

        for (itemRight of right) {
          let node = new TreeNode(i)
          node.left = itemLeft
          node.right = itemRight
          result.push(node)
        }
      }
    }

    return result
  }
  return helper(1, n)
};

三重循环是省不了了。不过可以加记忆化,提高运行速度。

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n <= 0) {
    return []
  }
  let map = {

  }
  function helper(m, n) {
    if (m == n) {
      return [new TreeNode(m)]
    }
    if (m > n) {
      return [null]
    }
    const key = `${m}${n}`
    if (key in map) {
      return map[key]
    }
    let result = []
    for (let i = m; i <= n; i++) {
      let left = helper(m, i - 1)
      let right = helper(i + 1, n)

      for (itemLeft of left) {

        for (itemRight of right) {
          let node = new TreeNode(i)
          node.left = itemLeft
          node.right = itemRight
          result.push(node)
        }
      }
    }
    map[key] = result
    return result
  }
  return helper(1, n)

};

不同的二叉搜索树

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

只是问有多少种,用动态规划求解。

每次把1..n的数分成两部分,左边的最后一个节点作为要节点。左右可以为空,这时就是null

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  let dp = new Array(n + 1).fill(0)
  //为空也是一种情况
  dp[0] = 1
  dp[1] = 1
  for (let i = 2; i <= n; i++) {
    //从1开始,分成两部分。左面最后一个节点做为根节点,所以左面是dp[j-1]
    //左面有多少种和右面有多少种相乘,就是j为根结点时的解。
    //从1到,n每个数都拿出来一次做根结点,加起来就是 1..n组成树的所有情况
    for (let j = 1; j <= i; j++) {
      dp[i] += dp[j - 1] * dp[i - j]
    }
  }
  return dp[n]
};

验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
  1. 中序遍历,应该是一个升序排列
  2. 递归判断左子树的最大值小于node.val,右子树的最小值大于node.val

递归有可以用返回最大最小值的形式也可以用传参数的形式

恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

  1. 用数组记录下每个结点的引用,找到不对的结点后,交换
  2. 用null记录返回的路径
  3. 找到第二个结点后,再次遍历找到第一个结点。

这个题还是挺细节的。三个指针保留状态。

finish标志位很重要,是一个优化,速度明显提高。

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {

  let left = null
  let right = null
  let pre = null
  let finish = false
  function helper(root) {
    if (!root || finish) return
    helper(root.left)

    if (pre && root.val < pre.val) {

      if (left) {
        //两个节点不相邻的情况
        right = root
        finish = true
      }
      else {
        left = pre
        //两个节点相邻的情况,不过还需要查找不相邻的情况
        right = root
      }
    }
    pre = root
    helper(root.right)
  }

  helper(root)
  let tmp = left.val
  left.val = right.val
  right.val = tmp
};

求根到叶子节点数字之和

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此,数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此,数字总和 = 495 + 491 + 40 = 1026.
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {

  let sum = 0
  function helper(root, s) {
    if (!root) return
    if (!root.left && !root.right) {
         sum = sum + parseInt(`${s}${root.val}`)
      return
    }
    helper(root.left, `${s}${root.val}`)
    helper(root.right, `${s}${root.val}`)
  }
  helper(root, '')
  return sum

};

二叉树中的最大路径和

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

这道题还是很经典的。思路是依次拿出每个结点做根结点,计算每条经过根点的路径和的最大值。

先说下如何算单条路径最大值。相当于是算[-1,2,3,4,-5] 必须包含3的和的最大值。从两边(左右子树)向中间靠拢。遇到小于0的就舍弃,只要有增加就加上(贪心)

当前结点算完后,从左右选一个大的和当前结点的值相加返回给上一层。

有一点注意的是 Math.max(root.val + left + right, max,root.val) 注意把当前结点自己加进和 'max'的比较,因为一个结点也是可以的。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  let max = -Infinity
  function helper(root) {
    if (!root) return 0

    let left =Math.max( helper(root.left),0)
    let right =Math.max( helper(root.right),0)

    max = Math.max(root.val + left + right, max,root.val)

    return root.val + Math.max(left, right)

  }

  let v = helper(root)
  max = Math.max(max, v)

  return max
};

二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如: 给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:

[
  [15,7],
  [9,20],
  [3]
]

深度优先,然后reverse

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function (root) {
  let result = []
  function helper(root, level) {
    if (!root) return
    if (!result[level]) result[level] = []
    result[level].push(root.val)
    helper(root.left, level + 1)
    helper(root.right, level + 1)
  }
  helper(root, 0)
  return result.reverse()
};

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

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

每次二分构造左右子树。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  if(!nums.length) return null
  let rootIndex = parseInt(nums.length / 2)
  let root = new TreeNode(nums[rootIndex])
  root.left = sortedArrayToBST(nums.slice(0, rootIndex))
  root.right = sortedArrayToBST(nums.slice(rootIndex + 1))

  return root
};

平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

递归比较,发现大于1就终止。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {

  let isOk = true

  function helper(root) {
    if (!root) return 0
    if (!isOk) return 0
    let leftDepth = helper(root.left)
    let rightDepth = helper(root.right)

    if (Math.abs(leftDepth - rightDepth) > 1) {
      isOk = false
    }
    return 1 + Math.max(leftDepth, rightDepth)
  }
  helper(root)
  return isOk
};

二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.

解法很多。我采用了最直观的方法,广度优先,只要发现叶子结点,就结束

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
  if (!root) return 0
  let stack1 = []
  let stack2 = [root]
  let level = 0
  while (stack2.length) {
    stack1 = stack2
    stack2 = []
    level++
    for (let item of stack1) {
      if (item.left) {
        stack2.push(item.left)
      }
      if (item.right) {
        stack2.push(item.right)
      }
      if (!item.left && !item.right) {
        return level
      }

    }
  }
};

用了两个变量stack1,stack2,可以合成一个。首先记录本次数据的长度,循环本次长度后里德下次循环。

参考下面的代码

var minDepth = function(root) {
    if(!root) return 0;
    let depth = 1;
    let queue = [root];
    if(!root.left && !root.right) return depth;

    while(queue.length > 0 ){
      let queueLength = queue.length;

      for(let i = 0; i < queueLength; i++){
        let node = queue.shift();

        if(!node.left && !node.right) return depth;
        else{
          if(node.left) queue.push(node.left);
          if(node.right) queue.push(node.right);
        }
      }

      depth++;
    }

    return depth;
};

个人比较喜欢两个变量,感觉清晰一些

路径总和

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

需注意,可能没加到叶子结点就达到了目标和,所以需要判断是否已经到达路子节点。

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var pathSum = function (root, sum) {
  let find = false
  function helper(root, s) {
    if (!root || find) { return }
    s = s + root.val
    if (s === sum && !root.left && !root.right) {
      find = true
      return
    }
    helper(root.left, s)
    helper(root.right, s)
  }
  helper(root, 0)
  return find
};

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径

和上面的相比,需要把路径记录下来

速度打败91%,内存打败 61.54%,看来用这种数组的方式还是不错的。为什么只有这题提到了执行效果呢,因为用数组存储路径,用push,pop,较为常见,也得到了验证,可以优先考虑使用。

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function (root, sum) {
  let result = []
  function helper(root, s, item) {
    if (!root) { return }
    item.push(root.val)
    s = s + root.val
    if (s === sum && !root.left && !root.right) {
      result.push(item.slice())
    }
    helper(root.left, s, item)
    helper(root.right, s, item)
    item.pop()
  }
  helper(root, 0, [])
  return result
};

二叉树展开为链表

给定一个二叉树,原地将它展开为链表。

例如,给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题意:按前序遍历展开。

分别对左右子树进行链表化,然后左子树称支右边,把右子树接在左子树的最右结点上。

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  if (!root) return null

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

  if (left) {
    root.right = left
    while(left.right) left=left.right
    left.right = right
    root.left = null
  }

  return root
};

填充每个节点的下一个右侧节点指针

递归方式和常规的不同。是从中间劈开,然后左右向中间推进。

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  if(!root) return root
  function helper(root) {
    if (!root.left&&!root.right) return null
    let left = root.left
    let right = root.right
    left.next = right
    while (left.right) { 
      left = left.right
      right = right.left
      left.next = right
    }
    helper(root.left)
    helper(root.right)
  }
  helper(root)
  return root
};

填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

进阶:

你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

做这道题花了不少心思,主要难在常数空间上。和上面的完美树不同,普通树的寻找路径是不确定的,只好借助辅助函数,帮助找到相近的点,总的思想和上面的一样,就是在查找相邻点上面有点不同

执行用时 96 ms, 在所有 JavaScript 提交中击败了85.71% 的用户 内存消耗 40.8 MB, 在所有 JavaScript 提交中击败了100.00% 的用户

var connect = function (root) {
  if (!root) return root
  function find(root, DEPTH, isLeft) {
    let result = null

    function helper(root, depth) {
      if (!root || result) return

      if (depth === DEPTH) {
        result = root
        return
      }
      if (isLeft) {
        helper(root.right, depth + 1)
        helper(root.left, depth + 1)
      }
      else {
        helper(root.left, depth + 1)
        helper(root.right, depth + 1)
      }
    }
    helper(root, 1)
    return result

  }

  function helper(root) {
    if (!root) return
    let depth = 1
    let left = root.left
    let right = root.right
    while (left && right) {
      left.next = right
      depth++
      left = find(root.left, depth, true)
      right = find(root.right, depth, false)
    }
    helper(root.left)
    helper(root.right)
  }
  helper(root)
  return root
}

二叉树的前序遍历

给定一个二叉树,返回它的 前序 遍历。递归,非递归算法

//非递归
var preorderTraversal = function (root) {
  let result = []

  let stack = []
  let cur = root

  //尝试右边后cur可能为空,看stack还有没有节点
  //curr为空,会略过while(cur),再pop一个节点,尝试右子树
  while (cur || stack.length) {
    //向左延伸到最左
    while (cur) {
      result.push(cur.val)
      //每次记录路径
      stack.push(cur)
      cur = cur.left
    }
    //左遇到null就回退
    cur = stack.pop()
    //尝试右边
    cur = cur.right
  }
  return result
};

//递归
var preorderTraversal = function(root) {
  let result = []
  function helper(root) {
      if(!root) return  
    result.push(root.val)
    helper(root.left)
    helper(root.right)
  }
  helper(root)
  return result
};

二叉树的后序遍历 给定一个二叉树,返回它的 后序 遍历。

递归就不说了,说下非递归写法。想好好久,感觉象是前面有个悬崖,怎么也上不去,突然灵光一闪,就解了。所以能不能想不来,很大程度是看有没有决心,有没有全身心的投入,不计成本的投入。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  let result = []
  let stack = []

  let cur = root
  while (stack.length || cur) {
    while (cur) {
      stack.push(cur)
      result.push(cur.val)
      cur = cur.right
    }  
    cur = stack.pop()
    cur=cur.left
  }
  return result.reverse()
};

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)