东哥带你刷二叉树（纲领篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉树（纲领篇）

评论礼仪 见这里，违者直接拉黑。

[Deserant]

牛蛙牛蛙占个楼

[houhuawei23]

东哥yyds!!!

[deepbreath373]

学到不少 NICE

[Asber777]

你只需要思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会对所有节点做相同的操作。

遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历.

[labuladong]

@Asber777 这个总结很好

[a572251465]

666

[xiazhi1]

感觉搜索二叉树深度第一个解法，不能用全局变量，要通过指针来传递res，depth

[1181406961]

刷了一些算法吧，刷二叉树类问题确实是承前启后。遍历解法，深一步就是回溯思想。分解子问题解法，深一步就是动态规划。

[jswxwxf]

js 版二叉树直径：

var diameterOfBinaryTree = function(root) {
  let maxDiameter = 0;
  // 对每个节点计算直径，求最大直径
  maxDepth(root);
  return maxDiameter;

  // 计算二叉树的最大深度
  function maxDepth(root) {
    if (root == null) {
      return 0;
    }
    const leftMax = maxDepth(root.left);
    const rightMax = maxDepth(root.right);
    // 后序位置顺便计算最大直径
    const myDiameter = leftMax + rightMax;
    maxDiameter = Math.max(maxDiameter, myDiameter);

    return Math.max(leftMax, rightMax) + 1;
  }
};

[jswxwxf]

二叉树的简单 js 实现，可以用来调试代码：

class TreeNode {
  constructor(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  insert(values) {
    const queue = [this];
    let i = 0;
    while (queue.length > 0) {
      let current = queue.shift();
      for (let side of ["left", "right"]) {
        if (!current[side]) {
          if (values[i] !== null) {
            current[side] = new TreeNode(values[i]);
          }
          i++;
          if (i >= values.length) return this;
        }
        if (current[side]) queue.push(current[side]);
      }
    }
    return this;
  }
}

const tree = new TreeNode(15);
tree.insert([1, 2, 3, 4, 3, 8, 7, 5, 10, 12, 11, null, null, null]);

[jswxwxf]

js 二叉树分治前序遍历

function preorderTraverse(root) {
  const res = [];
  if (root == null) {
    return res;
  }
  // 前序遍历的结果，root.val 在第一个
  res.push(root.val);
  // 利用函数定义，后面接着左子树的前序遍历结果
  res.push(...preorderTraverse(root.left));
  // 利用函数定义，最后接着右子树的前序遍历结果
  res.push(...preorderTraverse(root.right));
  return res;
}

[StormWangxhu]

牛逼

[uncle-leeeeee]

坚持学习！

[polaris-dxz]

515 的题其实利用层序遍历有一种更通用的模板：

var largestValues = function(root) {
    const level = []
    const traverse = (root, depth) => {
        if(!root) return
        if(!level[depth]) level[depth] = []
        traverse(root.left, depth+1)
        level[depth].push(root.val)
        traverse(root.right, depth+1)
    }
    traverse(root, 0)
    const ans = level.map(arr => Math.max.apply(null, arr))
    return ans
};

[cold-runner]

求二叉树深度那里还是不太理解为什么在离开结点之前depth要自减一次

[cold-runner]

啊！突然懂了，左孩子已经执行了一次depth++，在离开结点之前，右孩子也进行了depth++，该层的depth加了两次，所以离开前要让depth自减一次以维护。

[chxclyde]

我觉得你的理解有点问题，因为有可能右孩子不存在。作者这里说得很清楚。

因为前面说了，前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，depth 记录当前递归到的节点深度，你把 traverse 理解成在二叉树上游走的一个指针，所以当然要这样维护。

我的理解是你需要维护depth作为一个invariant一直是当前节点的深度，离开一个节点到上一层的时候深度自然需要减少

[StarrySeas1]

你好，既然你说了所有算法都是枚举，那为了方便理解，是不是应该从枚举解法出发，一步一步优化到最优算法，这样讲解是不是更好理解些，而不是上来就给最优解法，大部分最优解法如果没有经过专业训练是想不起来的。
枚举在大多数情况下是最直观的方法，也是大部分人更容易想到的，有逻辑的东西才学的快，记得牢，以下跳到最优解法是不科学的。

[buddy-source]

二叉树的层次遍历不属于递归吧？？

[buddy-source]

我懂了

[hmt990410]

感觉没有代码随想录说的清楚

[Chenxianzhi]

感谢博主，学到了很多，但看完并非能够砍瓜切菜，博文在行文上自认为存在一些跳跃性，导致还是存在一些疑惑。不论如何，感谢。

[HenryWD]

104 遍历思路的Python代码好像有点问题，说是全局变量depth没有定义。
traverse函数里 depth += 1 那一行报错了

在stackoverflow上查了，说是在函数内部变量的前面要加个'global'。楼主的gpt代码也是这么做的呀，但还是报错了。

有人知道是leetcode运行的问题还是语法不规范吗？ 谢谢🙏

res = depth = 0

def maxDepth(self, root: Optional[TreeNode]) -> int:
    
    self.traverse(root)
    return res


def traverse(self,root):
    global res, depth

    if root == None: return 
    
    depth += 1
    if root.left == None and root.right == None:
        res = max(res,depth)
    
    self.traverse(root.left)
    self.traverse(root.right)

    depth -= 1

[HenryWD]

另外想问一下这个题目遍历思路下可以把代码整合到主函数里吗？
如果要整合，该怎么定义变量呢？代码该怎么改呢？

[labuladong]

文中代码的作用是讲解算法思路，不是完整的可运行代码。不要在 solution class 外创建全局变量，python 可以在 class 内部用 self.xxx 的方式定义实例字段，参考我的 java 代码实现。

[ghost]

请问东哥用的画图工具是什么呀？

[Andywjw]

hhy必进大厂

[Sunsunsun87]

我觉得树深度那道题的遍历思路和分解问题思路，只不过是从根到叶子与叶子到根两个递推的方向罢了，本质是一样的，遍历和分解问题没有什么区别。

[shiboys]

横向遍历求每层的最大值, 就是宽度优先遍历，非递归版：

 public List<Integer> traverseMaxLevel(TreeNode root) {
        List<Integer> maxLevelValRes = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> levelValues = new ArrayList<>(sz);
            for (int i = 0; i < sz; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            maxLevelValRes.add(levelValues.stream().max((a, b) -> {
                return a - b;
            }).get());
        }
        return maxLevelValRes;
    }

[shiboys]

中间如果去掉集合改用局部变量，则 leetcode 的提交表明从 8ms 降低到 2ms，性能大幅提升

public List<Integer> traverseMaxLevel(TreeNode root) {
        List<Integer> maxLevelValRes = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int sz = queue.size();
            int maxLevel = Integer.MIN_VALUE;
            for (int i = 0; i < sz; i++) {
                TreeNode node = queue.poll();
                maxLevel = Math.max(maxLevel,node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            maxLevelValRes.add(maxLevel);
        }
        return maxLevelValRes;
    }

[Xiaodiudiudiu]

树的视角看backtrack的cpp修改：

void backtrack(int[] nums) {
// 回溯算法框架
for (int i = 0; i < nums.length; i++) {
if (used[i] == true) continue; // 如果这个元素已经被选择过，则跳过

    // 做选择
    used[i] = true;
    track.addLast(nums[i]);

    // 进入下一层回溯树
    backtrack(nums);

    // 取消选择
    track.removeLast();
    used[i] = false;
}

}

[DreamYuki]

打卡，前序中序后序就好像生命周期的钩子函数，判定不同的条件可以千变万化，但实际上还是同一套框架

[LeilaWhitman]

总感觉回溯和DFS是一个东西，写在for里面和for外面差不多。但根节点的处理可能有差异

[LeilaWhitman]

哦哦，明白了，图论基础那里说了回溯会漏掉根节点。回溯和DFS 实际上就是 处理边和处理点的关系。回溯关注的是边，边数=点数-1（无环图成立，但是回溯等一般的 图算法都会visited掉环，所以对回溯是永远会漏掉根节点（大概？））

[CZT0]

104二叉树的最大深度中golang的代码有问题，使用了全局变量 res 和 depth，在连续调用 maxDepth 函数时可能会出现问题。这是因为 res 和 depth 的值在两次函数调用之间没有被重置，导致它们保留了上一次函数调用的状态。
可以让traverse 函数返回当前节点的深度。每次递归调用时，深度加1，并在返回时比较左右子树的深度，返回较大的一个。这样就不需要全局变量，而是通过递归调用的返回值来计算深度。

func maxDepth(root *TreeNode) int {
    return traverse(root, 0)
}

func traverse(root *TreeNode, deep int) int {
    if root == nil {
        return deep
    }

    deep++

    leftDepth := traverse(root.Left, deep)
    rightDepth := traverse(root.Right, deep)

    if leftDepth > rightDepth {
        return leftDepth
    }
    return rightDepth
}

[CZT0]

这个就是第二种解题思路，第一种解题思路运行会报错

[excai]

关于文章结尾“优秀读者的递归进行层序遍历方法”多说两句。原文中的方法使用C++的queue来pop旧层push进新层，相当于C数组中结尾添加然后移动标志（c数组做circular buffer可以近似queue的效果）。结尾的方法是保留旧的queue添加新的queue，类似于C使用临时Node数组记录新层（可以用memcpy覆盖旧数组来节约空间）。

绕来绕去，关注点似乎跑到了如何用C模拟C++ queue上

[ImZzBy]

“如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？”
这个问题，我的第一个想法是改造前文讲的求二叉树深度的代码。

试了下，把和res有关的代码去掉就成。
回想确实是这样的，节点的层数等于节点的深度（深度从1开始算，且不是整棵树的深度），而depth所表示的恰恰就是深度，直接拿来用就行。

[ImZzBy]

理解有错欢迎指出，我也是第一次学，摸着石头过河来着