广度优先搜索（层序），深度优先搜索（前序（递归、迭代）、中序（递归、迭代、莫里斯）、后序（递归、迭代））遍历树深度：求解《104. 二叉树的最大深度》

例题

104. 二叉树的最大深度

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

答案

广度优先搜索

class Solution {
public:
  int maxDepth(TreeNode* root) { // 广度优先搜索
    if (root == nullptr) return 0;
    int maxDepth = 0, depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (q.empty() == false) {
      int l = q.size();
      maxDepth = max(maxDepth, ++depth);
      while (l--) {
        TreeNode* n = q.front();
        q.pop();
        if (n->left != nullptr) q.push(n->left);
        if (n->right != nullptr) q.push(n->right);
      }
    }
    return maxDepth;
  }
};

function maxDepth(root: TreeNode | null): number { // 广度优先搜索
  if (root == null) return 0
  const q = [root]
  let i = 0, depth = 0, maxDepth = 0
  while (i < q.length) {
    depth++
    for (let l = q.length; i < l; i++) {
      const n = q[i]
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
    if (maxDepth < depth) maxDepth = depth
  }
  return maxDepth
};

深度优先搜索 · 前序遍历 · 递归

func maxDepth(root *TreeNode) int { // 深度优先搜索 · 前序遍历 · 递归 
  if root == nil {
    return 0
  }
  var d func(n *TreeNode, depth int) int
  d = func(n *TreeNode, depth int) int {
    if n == nil {
      return depth
    }
    return max(d(n.Left, depth + 1), d(n.Right, depth + 1))
  }
  return d(root, 0)
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

int maxDepth(struct TreeNode* root){ // 深度优先搜索 · 前序遍历 · 递归
  if (root == NULL) return 0;
  return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

int maxDepth(struct TreeNode* root){ // 深度优先搜索 · 前序遍历 · 递归
  return d(root, 0);
}
int d(struct TreeNode* n, int depth) {
  if (n == NULL) return depth;
  return fmax(d(n->left, depth + 1), d(n->right, depth + 1));
}

class Solution(object): # Python 2.7.12
  def maxDepth(self, root): # 深度优先搜索 · 前序遍历 · 递归
    if root == None: return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

深度优先搜索 · 前序遍历 · 单栈

class Solution {
  function maxDepth($root) { // 深度优先搜索 · 前序遍历 · 单栈
    if ($root == null) return 0;
    $stack = [$root];
    $root->depth = 1;
    $maxDepth = 0;
    while (count($stack) > 0) {
      $n = array_pop($stack);
      $maxDepth = max($maxDepth, $n->depth);
      if ($n->right) {
        $stack []= $n->right;
        $n->right->depth = $n->depth + 1;
      }
      if ($n->left) {
        $stack []= $n->left;
        $n->left->depth = $n->depth + 1;
      }
    }
    return $maxDepth;
  }
}

深度优先搜索 · 中序遍历 · 递归

class Solution {
public:
  int r = 0;
  int maxDepth(TreeNode* root) { // 深度优先搜索 · 中序遍历 · 递归
    d(root, 1);
    return r;
  }
  void d(TreeNode* n, int depth) {
    if (n == nullptr) return;
    d(n->left, depth + 1);
    r = max(r, depth);
    d(n->right, depth + 1);
  }
};

深度优先搜索 · 中序遍历 · 单栈

public class Solution {
  private Dictionary<TreeNode, int> depth = new Dictionary<TreeNode, int>();
  public int MaxDepth(TreeNode root) { // 深度优先搜索 · 中序遍历 · 单栈
    if (root == null) return 0;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    depth.Add(root, 1);
    TreeNode p = root;
    int maxDepth = 1;
    while (stack.Count > 0 || p != null) {
      while (p != null) {
        stack.Push(p);
        updateDepth(p.left, depth[p] + 1);
        p = p.left;
      }
      TreeNode n = stack.Pop();
      maxDepth = Math.Max(maxDepth, depth[n]);
      p = n.right;
      updateDepth(p, depth[n] + 1);
    }
    return maxDepth;
  }
  public void updateDepth(TreeNode n, int curDepth) {
    if (n != null && depth.ContainsKey(n) == false) {
      depth.Add(n, curDepth);
    }
  }
}

深度优先搜索 · 中序遍历 · 莫里斯

var maxDepth = function(root) { // 深度优先搜索 · 中序遍历 · 莫里斯遍历
  if (root === null) return 0
  const depth = new Map
  depth.set(root, 1)
  let maxDepth = 1
  while (root) {
    const rootDepth = depth.get(root)
    if (root.left) {
      let p = root.left
      while (p.right !== null && p.right !== root) p = p.right
      if (p.right === null) {
        p.right = root
        root = root.left
      } else {
        p.right = null
        root = root.right
      }
    } else {
      root = root.right
    }
    if (root && depth.has(root) === false) {
      depth.set(root, rootDepth + 1)
      maxDepth = Math.max(maxDepth, depth.get(root))
    }
  }
  return maxDepth
};

深度优先搜索 · 后序遍历 · 递归

class Solution {
  private int r = 0;
  public int maxDepth(TreeNode root) { // 深度优先搜索 · 后序遍历 · 递归
    if (root == null) return 0;
    d(root, 1);
    return r;
  }
  public void d(TreeNode n, int depth) {
    if (n == null) return;
    d(n.left, depth + 1);
    d(n.right, depth + 1);
    r = Math.max(r, depth);
  }
}

深度优先搜索 · 后序遍历 · 单栈

class Solution: # Python 3.10
  def maxDepth(self, root: Optional[TreeNode]) -> int: # 后序遍历 · 单栈
    if root == None: return 0
    stack, p, prev, depth, maxDepth = [], root, None, {}, 1
    depth[root] = 1
    def updateDepth(n: Optional[TreeNode], curDepth: int):
      if n and n not in depth: depth[n] = curDepth
    while len(stack) or p :
      while p:
        stack.append(p)
        updateDepth(p.left, depth[p] + 1)
        p = p.left
      n = stack.pop()
      if n.right == None or n.right == prev:
        maxDepth = max(maxDepth, depth[n])
        prev = n
      else:
        stack.append(n)
        p = n.right
        updateDepth(p, depth[n] + 1)
    return maxDepth