广度优先搜索（层序遍历），深度优先搜索（前序、中序、后序，包含莫里斯遍历）递归和迭代（单栈、双栈），求解《1302. 层数最深叶子节点的和》

var deepestLeavesSum = function(root) { // 队列 + shift + 实现
  const q = [root]
  let sum = 0
  while (q.length) {
    let l = q.length
    sum = 0
    while (l--) {
      const n = q.shift()
      sum += n.val
      if (n.left) q.push(n.left) 
      if (n.right) q.push(n.right)
    }
  }
  return sum
}; 

function deepestLeavesSum(root: TreeNode | null): number { // 队列 + 指针 + 实现
  const q = [root]
  let start = 0, end = 1, sum = 0
  while (start < end) {
    let l = end
    sum = 0
    while (start < l) {
      const n = q[start++]
      sum += n.val
      if (n.left) q[end++] = n.left
      if (n.right) q[end++] = n.right
    }
  }
  return sum
};

class Solution {
  function deepestLeavesSum($root) {
    $q = [$root];
    $sum = 0;
    while (count($q)) {
      $l = count($q);
      $sum = 0;
      while ($l--) {
        $n = array_shift($q);
        $sum += $n->val;
        if ($n->left) array_push($q, $n->left);
        if ($n->right) array_push($q, $n->right);
      }
    }
    return $sum;
  }
}

func deepestLeavesSum(root *TreeNode) int {
  q, sum := []*TreeNode{root}, 0
  for len(q) > 0 {
    l := len(q)
    sum = 0
    for l > 0 {
      l--
      n := q[0]
      sum += n.Val
      q = q[1:]
      if n.Left != nil {
        q = append(q, n.Left)
      }
      if n.Right != nil {
        q = append(q, n.Right)
      }
    }
  }
  return sum
}

class Solution {
  public int deepestLeavesSum(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<TreeNode>();
    q.add(root);
    int sum = 0;
    while (q.isEmpty() == false) {
      int l = q.size();
      sum = 0;
      while (l-- > 0) {
        TreeNode n = q.pollFirst();
        sum += n.val;
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
      }
    }
    return sum;
  }
}

public class Solution {
  public int DeepestLeavesSum(TreeNode root) {
    Queue<TreeNode> q = new Queue<TreeNode>();
    q.Enqueue(root);
    int sum = 0;
    while (q.Count > 0) {
      int l = q.Count;
      sum = 0;
      while (l-- > 0) {
        TreeNode n = q.Dequeue();
        sum += n.val;
        if (n.left != null) q.Enqueue(n.left);
        if (n.right != null) q.Enqueue(n.right);
      }
    }
    return sum;
  }
}

int deepestLeavesSum(struct TreeNode* root){
  struct TreeNode** q = malloc(sizeof(struct TreeNode*) * 1e4);
  q[0] = root;
  int start = 0, end = 1, sum = 0;
  while (start < end) {
    int l = end;
    sum = 0;
    while (start < l) {
      struct TreeNode* n = q[start++];
      sum += n->val;
      if (n->left) q[end++] = n->left;
      if (n->right) q[end++] = n->right;
    }
  }
  return sum;
}

class Solution {
public:
  int deepestLeavesSum(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int sum = 0;
    while (q.size()) {
      int l = q.size();
      sum = 0;
      while (l--) {
        TreeNode* n = q.front();
        q.pop();
        sum += n->val;
        if (n->left) q.push(n->left);
        if (n->right) q.push(n->right);
      }
    }
    return sum;
  }
};

class Solution: # List 实现
  def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
    q, ans = [root], 0
    while len(q):
      l, ans = len(q), 0
      while l:
        l, n = l - 1, q.pop(0)
        ans += n.val
        if n.left: q.append(n.left)
        if n.right: q.append(n.right)
    return ans

class Solution: # deque 实现
  def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
    q = deque([root])
    while q:
      ans = 0
      for _ in range(len(q)):
        n = q.popleft()
        ans += n.val
        if n.left: q.append(n.left)
        if n.right: q.append(n.right)
    return ans

var deepestLeavesSum = function(root) {
  let sum = [], maxDepth = -1
  ;(function d(n, depth) {
    if (n === null) return maxDepth = Math.max(maxDepth, depth - 1);
    d(n.left, depth + 1)
    d(n.right, depth + 1)
    if (maxDepth === depth) sum[depth] = (sum[depth] || 0) + n.val
  })(root, 0)
  return sum[sum.length - 1]
};

var deepestLeavesSum = function(root) {
  let sum = 0, maxDepth = -1, curMaxDepth = -1
  ;(function d(n, depth) {
    if (n === null) return maxDepth = Math.max(maxDepth, depth - 1);
    d(n.left, depth + 1)
    d(n.right, depth + 1)
    if (maxDepth === depth) {
      if (curMaxDepth === depth) sum += n.val
      else {
        curMaxDepth = depth
        sum = n.val
      }
    }
  })(root, 0)
  return sum
};

function deepestLeavesSum(root: TreeNode | null): number {
  const stack = []
  let p = root, prev = null, depths = new Map, maxDepth = -1, sum = 0
  depths.set(root, 0)
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      updateDepth(depths, p.left, p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const depth = depths.get(n)
      if (n.right === null && n.left === null) {
        if (depth === maxDepth) sum += n.val
        else if (depth > maxDepth) {
          sum = n.val
          maxDepth = depth
        }
      }
      prev = n
    } else {
      stack.push(n)
      updateDepth(depths, n.right, n)
      p = n.right
    }
  }
  return sum
};
function updateDepth(depths, n, prev) {
  if (depths.has(n) === false) depths.set(n, depths.get(prev) + 1)
}

class Solution {
  public int deepestLeavesSum(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    Map<TreeNode, Integer> depths = new HashMap<TreeNode, Integer>();
    TreeNode p = root, prev = null;
    depths.put(root, 0);
    int maxDepth = -1, sum = 0;
    while (stack.size() > 0 || p != null) {
      while (p != null) {
        stack.push(p);
        update(depths, p.left, p);
        p = p.left;
      }
      TreeNode n = stack.pop();
      if (n.right == null || n.right == prev) {
        if (n.right == null && n.left == null) {
          int depth = depths.get(n);
          if (maxDepth < depth) {
            maxDepth = depth;
            sum = n.val;
          } else if (maxDepth == depth) {
            sum += n.val;
          }
        }
        prev = n;
      } else {
        stack.push(n);
        update(depths, n.right, n);
        p = n.right;
      }
    }
    return sum;
  }
  public void update(Map<TreeNode, Integer> depths, TreeNode n, TreeNode prev) {
    if (depths.containsKey(n) == false) depths.put(n, depths.get(prev) + 1);
  }
}