3
    / \
   9   20
  /   /  \
 8   15   7

sum = 12

解法一其实本质上就是做了DFS，我们知道DFS可以用栈去模拟。对于这道题，我们可以像解法二的BFS一样，再增加一个栈，去保存从根节点到当前节点累计的和就可以了。

原因就是我们进行的是中序遍历，当我们还没访问右边的节点的时候，根节点已经出栈了，再访问右边节点的时候，curSum就会少一个根节点的值。

所以，我们可以用后序遍历，先访问左子树，再访问右子树，最后访问根节点。再看一下上边的问题。

     3
    / \
   9   20
  / \   
 8   15   

curSum = 0
3 入栈， curSum = 3，3
9 入栈， curSum = 12，3 -> 9
8 入栈， curSum = 20， 3 -> 9 -> 8
8 出栈， curSum = 12， 3 -> 9
15 入栈， curSum = 27， 3 -> 9 -> 15

此时路径 3 -> 9 -> 15 对应的 curSum 就是正确的了。

用栈实现后序遍历，比中序遍历要复杂一些。当访问到根节点的时候，它的右子树可能访问过了，那就把根节点输出。它的右子树可能没访问过，我们需要去遍历它的右子树。所以我们要用一个变量pre保存上一次遍历的节点，用来判断当前根节点的右子树是否已经遍历完成。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    Stack<TreeNode> toVisit = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;

    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根节点
            cur = cur.left; // 递归添加左节点
        }
        cur = toVisit.peek(); // 已经访问到最左的节点了
        // 在不存在右节点或者右节点已经访问过的情况下，访问根节点
        if (cur.right == null || cur.right == pre) {
            toVisit.pop();
            result.add(cur.val);
            pre = cur;
            cur = null;
        } else {
            cur = cur.right; // 右节点还没有访问过就先访问右节点
        }
    }
    return result;
}

有了上边的后序遍历，对于这道题，代码就很好改了。

public boolean hasPathSum(TreeNode root, int sum) { 
    Stack<TreeNode> toVisit = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;
    int curSum = 0; //记录当前的累计的和
    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根节点
            curSum += cur.val;
            cur = cur.left; // 递归添加左节点
        }
        cur = toVisit.peek(); // 已经访问到最左的节点了
        //判断是否满足条件
        if (curSum == sum && cur.left == null && cur.right == null) {
            return true;
        }
        // 在不存在右节点或者右节点已经访问过的情况下，访问根节点
        if (cur.right == null || cur.right == pre) {
            TreeNode pop = toVisit.pop();
            curSum -= pop.val; //减去出栈的值
            pre = cur;
            cur = null;
        } else {
            cur = cur.right; // 右节点还没有访问过就先访问右节点
        }
    }
    return false;
}

总

这道题还是在考二叉树的遍历，DFS，BFS。解法三通过后序遍历节省了sum栈，蛮有意思的。

作者：windliang

来源：https://windliang.cc