广度优先搜索（层序），深度优先搜索（前序（递归、迭代）、中序（递归、迭代、莫里斯）、后序（递归、迭代））遍历：求解《404. 左叶子之和》

例题

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。 示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

答案

广度优先搜索

class Solution {
  function sumOfLeftLeaves($root) { // 广度优先搜索
    $q = [$root];
    $head = $sum = 0;
    $tail = 1;
    while($head < $tail) {
      $n = $q[$head++];
      if ($this->isLeafNode($n->left)) $sum += $n->left->val;
      if ($n->left) $q[$tail++] = $n->left;
      if ($n->right) $q[$tail++] = $n->right;
    }
    return $sum;
  }
  function isLeafNode($n) {
    return $n !== null && $n->left === null && $n->right === null;
  }
}

bool isLeafNode(struct TreeNode* n) {
  return n->left == NULL && n->right == NULL;
}
int sumOfLeftLeaves(struct TreeNode* root){ // 广度优先搜索
  struct TreeNode** q = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1009);
  q[0] = root;
  int head = 0, tail = 1, sum = 0;
  while (head < tail) {
    struct TreeNode* n = q[head++];
    if (n->left) {
      if (isLeafNode(n->left)) sum += n->left->val;
      q[tail++] = n->left;
    }
    if (n->right) q[tail++] = n->right;
  }
  return sum;
}

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

var sumOfLeftLeaves = function(root) { // 深度优先搜索 · 前序遍历 · 递归
  if (root === null) return 0
  return (isLeafNode(root.left) ? root.left.val : sumOfLeftLeaves(root.left)) + sumOfLeftLeaves(root.right)
};
const isLeafNode = n => n !== null && n.left === null && n.right === null

var sumOfLeftLeaves = function(root) { // 深度优先搜索 · 前序遍历 · 递归
  let sum = 0
  const d = n => {
    if (n === null) return
    if (isLeafNode(n.left) === true) sum += n.left.val
    d(n.left)
    d(n.right)
  }
  d(root)
  return sum
};
const isLeafNode = n => n !== null && n.left === null && n.right === null

class Solution { // 深度优先搜索 · 前序遍历 · 递归
public:
  int sumOfLeftLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    return (isLeafNode(root->left) ? root->left->val : sumOfLeftLeaves(root->left)) + sumOfLeftLeaves(root->right);
  }
  bool isLeafNode(TreeNode* n) {
    return n != nullptr && n->left == nullptr && n->right == nullptr;
  }
};

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

function sumOfLeftLeaves(root: TreeNode | null): number { // 深度优先搜索 · 前序遍历 · 迭代 · 单栈
  const stack = [root]
  let sum = 0
  while (stack.length) {
    const n = stack.pop()
    if (isLeafNode(n.left)) sum += n.left.val
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return sum
};
const isLeafNode = (n: TreeNode | null): boolean => {
  return n !== null && n.left === null && n.right === null
}

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

func sumOfLeftLeaves(root *TreeNode) int { // 深度优先搜索 · 中序遍历 · 递归
  sum := 0
  var d func(n *TreeNode)
  d = func(n *TreeNode) {
    if n == nil {
      return
    }
    d(n.Left)
    if isLeafNode(n.Left) {
      sum += n.Left.Val
    }
    d(n.Right)
  }
  d(root)
  return sum
}
func isLeafNode(n *TreeNode) bool {
  return n != nil && n.Left == nil && n.Right == nil
}

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

class Solution { // 深度优先搜索 · 中序遍历 · 单栈
public:
  int sumOfLeftLeaves(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    int sum = 0;
    while (s.empty() == false || p) {
      while (p) {
        s.push(p);
        p = p->left;
      }
      TreeNode* n = s.top();
      s.pop();
      if (isLeafNode(n->left)) sum += n->left->val;
      p = n->right;
    }
    return sum;
  }
  bool isLeafNode(TreeNode* n) {
    return n != nullptr && n->left == nullptr && n->right == nullptr;
  }
};

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

public class Solution {
  private int sum = 0;
  public int SumOfLeftLeaves(TreeNode root) { // 深度优先搜索 · 中序遍历 · 莫里斯遍历
    while (root != null) {
      if (root.left != null) {
        TreeNode 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;
          if (IsLeafNode(root.left)) sum += root.left.val;
          root = root.right;
        }
      } else {
        if (IsLeafNode(root.left)) sum += root.left.val;
        root = root.right;
      }
    }
    return sum;
  }
  public bool IsLeafNode(TreeNode n) {
    return n != null && n.left == null && n.right == null;
  }
}

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

class Solution(object):
  def isLeafNode(self, n):
    return n != None and n.left == None and n.right == None
  def sumOfLeftLeaves(self, root): # 深度优先搜索 · 后序遍历 · 递归
    ans = [0]
    def d(n):
      if n == None: return
      d(n.left)
      if self.isLeafNode(n.left): ans[0] += n.left.val
      d(n.right)
    d(root)
    return ans[0]

class Solution: # Python 3.10
  def isLeafNode(self, n) -> bool:
    return n != None and n.left == None and n.right == None
  def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: # 深度优先搜索 · 后序遍历 · 递归
    ans = 0
    def d(n):
      nonlocal ans
      if n == None: return
      d(n.left)
      if self.isLeafNode(n.left): ans += n.left.val
      d(n.right)
    d(root)
    return ans

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

class Solution { // 深度优先搜索 · 后序遍历 · 迭代 · 单栈
  private int sum = 0;
  public int sumOfLeftLeaves(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode p = root;
    TreeNode prev = null;
    while (stack.isEmpty() == false || p != null) {
      while (p != null) {
        stack.push(p);
        p = p.left;
      }
      TreeNode n = stack.pop();
      if (n.right == null || n.right == prev) {
        if (isLeafNode(n.left)) sum += n.left.val;
        prev = n;
      } else {
        stack.push(n);
        p = n.right;
      }
    }
    return sum;
  }
  public boolean isLeafNode(TreeNode n) {
    return n != null && n.left == null && n.right == null;
  }
}