树相关模板题目

dfs

• lc100 相同的树
• lc101 验证对称二叉树
• lc226 翻转二叉树
• lc108 将有序数组转换为二叉搜索树
• lc110 验证平衡二叉树
• lc144 先序遍历
• lc145 后续遍历
• lc94 中序遍历

bfs

• lc102二叉树层序遍历
  • lc104最大深度
  • lc111 最小深度
  • lc103 二叉树的锯齿形层次遍历
  • lc107 二叉树的层次遍历

翻转二叉树dfs

题解

dfs 典型代表 通过深度优先遍历模板和一些操作完成的题目

dfs
核心

• root是对象所以是引用传递，不会随着进入新调用栈而内容重置；
• return返回值只供最后一次出栈函数返回用，靠递归过程中改变引用对象内容；

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {TreeNode}
  */
  var invertTree = function(root){
    if(!root) return null 
  const temp = root.right
  root.right = root.left
  root.left = temp
    invertTree(root.left)
  invertTree(root.right)
  return root
  }

二叉树层序遍历bfs

bfs 典型代表 通过广度优先遍历模板和一些操作完成的题目 bfs queue

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const res = [];
    if (!root) return res;
    const q = [];
    q.push(root);
    while (q.length !== 0) {
        const len = q.length; // q.length 是当前节点层序的节点数量
        const level = []
        // 获取第一个节点把值推入，如果有左右子节点推入队列，下一次for使用
        for (let i = 1; i <= len; ++i) {
            const node = q.shift();
            level.push(node.val) 
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
        res.push(level)
    }
    return res;
};

总结

用dfs做的用bfs也能做，不过是麻烦点，反之也是
记住这俩模板能解决下边这大部分的题