問題

Find the sum of all left leaves in a given binary tree.
給定一棵二叉樹，找出其所有的左葉子節(jié)點的值的和。

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思考

這題的關(guān)鍵在于如何找出所有的左葉子節(jié)點。而對于一棵二叉樹來說，想要找到其所有的左葉子節(jié)點，我想到的最直接的方式是遍歷這棵二叉樹，判斷訪問到的節(jié)點是否為左葉子節(jié)點來累加其值，即可得到答案。

解法一

根據(jù)我的想法，現(xiàn)在問題轉(zhuǎn)移到了如何遍歷獲取二叉樹的左葉子節(jié)點。而遍歷一棵二叉樹，自然而然的會想到用遞歸的方式，因為樹本身就是一個遞歸的結(jié)構(gòu)。

二叉樹的左葉子節(jié)點可能存在于它的左子樹和右子樹里。從這兩部分分別進行討論求出左葉子節(jié)點，再相加即得到所求。

• 如果二叉樹的左子樹是一個葉子節(jié)點，則不用繼續(xù)深入下去了，要找的就是它。
• 如果二叉樹的左子樹不是一個葉子節(jié)點，則遞歸調(diào)用此過程去獲取左子樹的左葉子節(jié)點的值。
• 而對于二叉樹的右子樹，則無論其是否是一個葉子節(jié)點都不會影響結(jié)果，直接遞歸調(diào)用獲取右子樹的左葉子節(jié)點值即可。

按照上述遞歸的思想，代碼如下：

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;//遞歸結(jié)束條件
    int left, right;
    if (root.left != null && root.left.left == null 
        && root.left.right == null) {//判斷是否為左葉子節(jié)點
        left = root.left.val;
    } else {
        left = sumOfLeftLeaves(root.left);
    }
    right = sumOfLeftLeaves(root.right);
    return left + right;
}

解法二

實際上，遍歷二叉樹的方式實在是太多了，前序遍歷、中序遍歷、后序遍歷、層級遍歷等等。遍歷二叉樹可以通過遞歸的方式，也可通過迭代的方式。（話說筆試面試中常常會問到樹的非遞歸遍歷...=_=）下面通過前序遍歷的迭代方式去遍歷二叉樹，累加左葉子節(jié)點的值來解決問題。

代碼如下：

public int sumOfLeftLeaves(TreeNode root) {
    TreeNode node = root;
    Stack<TreeNode> stack = new Stack<>();
    int sum = 0;
    while (node != null || !stack.isEmpty()) {

        while (node != null) {
            stack.push(node);
            if (node.left != null && node.left.left == null 
                && node.left.right == null) {
                sum += node.left.val;
            }
                node = node.left;
        }

        if (!stack.isEmpty()) {
            node = stack.pop().right;
        }
    }
    return sum;
}

通過一個輔助棧來實現(xiàn)二叉樹的非遞歸前序遍歷，在訪問到一個節(jié)點的時候去判斷它是否為左葉子節(jié)點即可。

下面再列出層級遍歷二叉樹的方式去求解的代碼：

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    int sum = 0;
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null && node.left.left == null 
            && node.left.right == null) {
            sum += node.left.val;
        }
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return sum;
}

思路是一致的，只是層級遍歷需要通過一個輔助隊列去實現(xiàn)而已。

總結(jié)

其實這題挺容易想出解決思路，將求和問題轉(zhuǎn)化為遍歷二叉樹的問題就行。在這里記錄下來，也是為了回顧一下二叉樹的幾種遍歷方式，主要是非遞歸的幾種遍歷的寫法。