概述及定义

树的高度&深度

节点的深度：指从根节点到该节点的最大简单路径边的条数。根节点深度为 1。
节点的高度：指从该节点到叶子节点的最长简单路径边的条数。根节点高度为根的最大高度，它的值也是树的最大深度。

关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。

平衡二叉树

一个高度平衡二叉树是指：每个节点的左右两个子树的高度差的绝对值不超过 1。

题目

144. 二叉树的前序遍历

一棵二叉树可以被左节点切分。
一棵二叉树遍历是有递归序存在的。每个节点一般会经过 3 次。
首先做的第一步就是走到左子树的末尾。在遍历过程中，将路过的根节点首先加入结果集合中。

遇到末尾，然后弹出栈，

class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
     List<Integer> res = new ArrayList<>();
     if (root == null) return res;
     Deque<TreeNode> stack = new ArrayDeque<>();
     TreeNode p = root;
     while (!stack.isEmpty() || p != null) {
         while (p != null) {
             stack.addLast(p);
             res.add(p.val);
             p = p.left;
         }
         TreeNode node = stack.pollLast();
         p = node.right;
     }
     return res;
 }
}

94. 二叉树的中序遍历

class Solution {
 public List<Integer> inorderTraversal(TreeNode root) {
     List<Integer> res = new ArrayList<>();
     if (root == null) return res;
     TreeNode p = root;
     Deque<TreeNode> stack = new ArrayDeque<>();
     while (!stack.isEmpty() || p != null) {
         while (p != null) {
             stack.addLast(p);
             p = p.left;
         }
         TreeNode node = stack.pollLast();
         res.add(node.val);
         p = node.right;
     }
     return res;
 }
}

145. 二叉树的后序遍历

使用 prev 指针指向最近处理过的节点。当节点的值添加到 res 集合中，就可以更新 prev 指针。
使用 prev 指针是为了判断某个根节点的右子树是否已经被处理过。如果没有处理那么将右子树的所有子节点都入栈，然后生产遍历。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        // 什么时候更新prev指针呢?
        // prev指针是指向上一次遍历过的节点
        TreeNode prev = null;
        while (p != null) {
            stack.addLast(p);
            p = p.left;
        }
        while (!stack.isEmpty()) {
            // 获取栈顶元素处理
            TreeNode node = stack.peekLast();
            // 1.处理右节点：遇到右节点不为空且右节点没有被遍历过，
            // 将右节点的所有子节点入栈
            if (node.right != null && node.right != prev) {
                // 没有遍历右节点，处理右节点
                p = node.right;
                while (p != null) {
                    stack.addLast(p);
                    p = p.left;
                }
            } else {
                // 1.遇到叶子节点
                // 2.当前节点的左右子节点已经处理完毕
                stack.pollLast();
                res.add(node.val);
                // 记住这么一件事，当添加res集合中，就可以更新prev指针了
                prev = node;
            }
        }
        return res;
    }
}

下面代码的思路和上面其实是一样的：

prev 指针指向上次添加到集合中元素的节点
指针 p 用来对右子树进行遍历的指针，在最后操作的时候需要清空，否则会无限循环

当遇到没有处理的右节点时，将指针 p 指向右节点，然后立即利用 continue 返回，将该右节点的所有左节点入栈，重复操作。

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      if (root == null) return  res;
      Deque<TreeNode> stack = new ArrayDeque<>();
      TreeNode prev = null;
      TreeNode p = root;
      while (!stack.isEmpty() || p != null) {
          while (p != null) {
              stack.addLast(p);
              p = p.left;
          }
          p = stack.peekLast();
          if (p.right != null && p.right != prev) {
              p = p.right;
              continue;
          }
          stack.pollLast();
          res.add(p.val);
          prev = p;
          // 记得重置p指针
          p = null;
      }
      return res;
  }
}

104. 二叉树的最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
当前节点的深度 = Math.max(左节点最大深度, 右节点最大深度) + 1。
求深度可以从上到下去查，所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。有的同学一定疑惑，为什么二叉树：看看这些树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。

111. 二叉树的最小深度
递归会有一个问题就是使用 Math.min() 比较的情况，需要根据左右子节点是否为null做进一步处理。 ```java class Solution { public int minDepth(TreeNode root) {
```
  if (root == null) return 0;
  if (root.left == null && root.right == null) return 1;
  int l = minDepth(root.right); 
  int l = minDepth(root.right); 
```

    int l = minDepth(root.left);
    int r = minDepth(root.right);
    return root.left == null || root.right = null ? 
}

}


```java
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        if (root.left == null && root.right == null) return 1;
        int l = minDepth(root.left);
        int r = minDepth(root.right);

        return root.left == null || root.right == null ? l + r + 1: 1 + Math.min(l, r);
    }
}

101. 对称二叉树

迭代思路

对称二叉树迭代思路.gif
对称二叉树迭代思路2.png

每次处理时只比较两个节点值。

边界条件。

class Solution {
 public boolean isSymmetric(TreeNode root) {
     if (root == null) return false;
     Deque<TreeNode> queue = new LinkedList<>();
     queue.addLast(root.right);
     queue.addLast(root.left);
     while (!queue.isEmpty()) {
         // 核心是每次只获取两个节点进行比较
         TreeNode left = queue.pollLast();
         TreeNode right = queue.pollLast();

         if (left == null && right == null) continue;
         if (left == null || right == null) return false;
         if (left.val != right.val) return false;
         // 不需要再对比子节点了
         queue.addLast(left.left);
         queue.addLast(right.right);
         queue.addLast(left.right);
         queue.addLast(right.left);
     }

     return true;
 }
}

递归思路

对称二叉树递归思路.png

首先，我们思考是比较两个节点，如上图所示，所以定义一个方法包含两个 TreeNode 参数。
如果确定递归序呢? 需要根据实际条件来判断，我们需要判断 left.left 和 right.right、left.right 和 right.left 是否相等。 ```java public boolean isSymmetric(TreeNode root) { return root==null || isSymmetricHelp(root.left, root.right); }

private boolean isSymmetricHelp(TreeNode left, TreeNode right){ if (left==null || right==null) return left==right; if (left.val != right.val) return false; return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left); }

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;

        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode l, TreeNode r) {
        if (l == null && r == null) return true;
        if (l == null || r == null) return false;
        if (l.val != r.val) return false;
        // 关键
        return compare(l.left, r.right) && compare(l.right, r.left);
    }
}

257. 二叉树的所有路径

问题：何时移除队列 path 中的元素。也就是回溯过程是什么时候发生的。什么时候 return，什么时候 remove。这需要对递归有一个更清楚的认识。 ```java class Solution { public List binaryTreePaths(TreeNode root) {

  List<String> res = new ArrayList<>();
  if (root == null) return res;
  Deque<Integer> path = new ArrayDeque<>();

  traversal(root, path, res);
  return res;

}

private void traversal(TreeNode root, Deque path, List res) {

  if (root == null) return ;
  path.add(root.val);
  // 走到叶子节点了
  if (root.left == null && root.right == null) {
      // 输出记录
      res.add(getStr(path));
  }

  traversal(root.left, path, res);
  traversal(root.right, path, res);
  path.removeLast();

}

private String getStr(Deque<Integer> path) {
    StringBuilder str = new StringBuilder();
    int size = path.size() - 1;
    int i = 0;
    for (Integer p : path) {
        str.append(p);
        if (i != size) {
            str.append("->");
        }
        i++;
    }
    return str.toString();
}

}

使用 `StringBuilder` 可以避免非叶子节点的拷贝，这样退化为链表时，时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/33697ce7dfa48ba80980d298c8089378.svg#card=math&code=O%28N%29&id=PNMzY)。最坏时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/c47686334b4d40f78bcf8743aa16c157.svg#card=math&code=O%28%5Cfrac%7BN%7D%7B2%7D%20%2B%20%5Cfrac%7BN%7D%7B2%7D%20%2A%20logN%29&id=tsTYj) ~ ![](https://cdn.nlark.com/yuque/__latex/7deeff9af96fe8fac40db184b1837f20.svg#card=math&code=O%28NlogN%29&id=ncEea)。

```java
public List<String> binaryTreePaths(TreeNode root) {
    List<String> answer = new ArrayList<String>();
    if (root != null) searchBT(root, "", answer);
    return answer;
}
private void searchBT(TreeNode root, String path, List<String> answer) {
    if (root.left == null && root.right == null) answer.add(path + root.val);
    if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
    if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
}

时间复杂度：每个节点都进行String的拷贝，那最坏情况出现在退化为链表的树时，这时候由于String长度与节点个数正相关，而每个节点都会进行拷贝，所以渐进复杂度为树 - 图9 。
空间复杂度：

优秀的解法

这里是在每层递归时使用一个 len 保存长度。

class Solution {
   public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        helper(res, root, sb);
        return res;
    }

    private void helper(List<String> res, TreeNode root, StringBuilder sb) {
        if(root == null) {
            return;
        }
        int len = sb.length();
        sb.append(root.val);
        if(root.left == null && root.right == null) {
            res.add(sb.toString());
        } else {
            sb.append("->");
            helper(res, root.left, sb);
            helper(res, root.right, sb);
        }
        // 恢复当前层的长度
        sb.setLength(len);
    }
}

404. 左叶子之和

public int sumOfLeftLeaves(TreeNode root, boolean isLeft) {
    if (root == null) return 0;
    if (isLeft == true && root.left == null && root.right == null) return root.val;
    return sumOfLeftLeaves(root.left, true) + sumOfLeftLeaves(root.right, false);
}

public int sumOfLeftLeaves(TreeNode root) {
    return sumOfLeftLeaves(root, false);
}

栈是能保存数据的，也就是能保存前一个函数调用的状态。所以这里使用一个布尔变量来保存当前节点是叶子节点还是非叶子节点，如果是非叶子节点的话，那么不会累加它的数据。
条件判断是复杂的，这里需要求的是左叶子节点，过滤掉右叶子节点，所以需要仔细想一下如何做好递归的判断条件：视角是一个根节点，要求根节点的左子节点不为空且左子节点的左、右节点都为空

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int sum = 0;
    if (root.left != null && root.left.left == null && root.left.right == null) {
        sum += root.left.val;
    }  else {
        sum += sumOfLeftLeaves(root.left);
    }
    sum += sumOfLeftLeaves(root.right);

    return sum;
}

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int leftVal = sumOfLeftLeaves(root.left);
    int rightVal = sumOfLeftLeaves(root.right);
    int sum = 0;
    if (root.left != null && root.left.left == null && root.left.right == null) {
        sum += root.left.val;
    }  

    return sum + leftVal + rightVal;
}

116. 填充每个节点的下一个右侧节点指针

这题主要的难点在于如果跨节点连接：
填充每个节点的下一个右侧节点指针.png

层序遍历

public Node connect(Node root) {
    if (root == null) return root;
    Deque<Node> queue = new ArrayDeque<>();
    queue.addLast(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node pre = null;
        while (size > 0) {
            Node node = queue.pollLast();
            if (node.right != null) queue.addFirst(node.right);
            if (node.left != null) queue.addFirst(node.left);
            node.next = pre;
            pre = node;
            size--;
        }
    }

    return root;
}

时间复杂度：树 - 图12 。每个节点都会被访问一次且只会被访问一次。
空间复杂度：树 - 图13 。广度优先遍历的复杂度取决于一个层级上的最大元素数据，这种情况下的空间复杂度为树 - 图14 。

遍历思路

按层处理每层节点的next指针。
这棵树是完美的二叉树。
填充每个节点的下一个右侧节点指针.gif

public Node connect(Node root) {
    if (root == null) return root;
    // 使用两个指针，感觉象是在按层遍历
    // pre 指针指向上一层节点，这一层节点已经完成节点next的赋值操作
    Node pre = root;

    // cur指针一开始会指向pre节点，然后对pre节点的下一层进行next指针赋值
    Node cur = null;

    while (pre.left != null) {
        cur = pre;
        while (cur != null) {
            // 赋值左节点
            cur.left.next = cur.right;

            // 根据自己的next指针判断是否需要赋值自己右孩子节点指针
            if (cur.next != null) 
                cur.right.next = cur.next.left;

            // 更新cur指针，遍历当前层的后序节点
            cur = cur.next;
        }

        // 更新pre指针，指向下一层
        pre = pre.left;
    }

    return root;
}

时间复杂度：树 - 图17
空间复杂度：树 - 图18

递归思路

递归思想是一个深度的视角，如下图所示：
填充每个节点的下一个右侧节点指针递归思路.png
关键点在于：

我们需要一开始连接 root 节点的左右子节点。
然后再判断父节点的 next 指针是否为 null，如果非 null ，说明需要进行对 root.right.next 进行赋值。

做好以上几点，剩下的就交给递归结构帮我们完成遍历

public Node connect(Node root) {
    if (root == null || root.left == null) return root;
    root.left.next = root.right;
    if (root.next != null) root.right.next = root.next.left;
    connect(root.left);
    connect(root.right);
    return root;
}

public Node connect(Node root) {
    if (root == null) return null;
    connection(root);
    return root;
}

public void connection(Node root){
    if (root.left == null) return;

    // 
    root.left.next = root.right;

    // 关键判断，当前节点的左孩子不为空，则其右孩子节点也一定不会为空
    if (root.next != null){
        root.right.next = root.next.left;
    }

    connection(root.left);
    connection(root.right);
}

时间复杂度：树 - 图20
空间复杂度：树 - 图21 ，h 是树的高度

114. 二叉树展开为链表

递归思路

二叉树展开为链表.png
思路比较简单，类似后序遍历，处理左右子节点后再处理根节点。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left != null && right != null) {
            root.right = left;
            root.left = null;

            TreeNode cur = left;
            while (cur.right != null) {
                cur = cur.right;
            }
            cur.right = right;

        } else if (root.left != null && root.right == null) {
            root.right = root.left;
            root.left = null;
        } 
    }
}

递归指针（解法更好）

// 利用一个全局变量prev，更新当前根节点的右指针为prev，左指针为null
private TreeNode prev = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

    1
   / \
  2   5
 / \   \
3   4   6
-----------        
pre = 5
cur = 4

    1
   / \
  2   \
 / \  |
3   4 |
     \|
      5
       \
        6
-----------        
pre = 4
cur = 3

    1
   / \
  2  |
 /|  | 
3 |  |
 \|  |
  4  |
   \ |
    5
     \
      6
-----------        
cur = 2
pre = 3

    1
   / \
  2   \
   \   \
    3   \
     \  |
      4 |
       \|
        5
         \
          6
-----------        
cur = 1
pre = 2

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

新奇解法

将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null ```java

1 / \ 2 5 / \ \ 3 4 6

//将 1 的左子树插入到右子树的地方 1 \ 2 5 / \ \ 3 4 6
//将原来的右子树接到左子树的最右边节点 1 \ 2
/ \
3 4
\ 5 \ 6

//将 2 的左子树插入到右子树的地方 1 \ 2
\
3 4
\ 5 \ 6

//将原来的右子树接到左子树的最右边节点

```java
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        TreeNode p = root;
        while ( p != null) {
            TreeNode left =  p.left;
            TreeNode right =  p.right;

            // 左节点不为空，需要把左节点合并到根节点的右子树中
            if (left != null) {
                p.right = left;
                p.left = null;
                while (left.right != null) {
                    left = left.right;
                }

                left.right = right;
            }

            // 更新 p 指针
             p =  p.right;
        }
    }
}

后序遍历思路

int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }
    dfs(root);
    return max;
}

/**
     * 返回经过root的单边分支最大和， 即Math.max(root, root+left, root+right)
     * @param root
     * @return
     */
public int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    //计算左边分支最大值，左边分支如果为负数还不如不选择
    int leftMax = Math.max(0, dfs(root.left));
    //计算右边分支最大值，右边分支如果为负数还不如不选择
    int rightMax = Math.max(0, dfs(root.right));
    //left->root->right 作为路径与已经计算过历史最大值做比较
    max = Math.max(max, root.val + leftMax + rightMax);
    // 返回经过root的单边最大分支给当前root的父节点计算使用
    return root.val + Math.max(leftMax, rightMax);
}

public class Solution {
    int maxValue;

    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }

    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

513. 找树左下角的值

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        Integer levelFirst = null;
        boolean hasSet = false;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            while (queueSize > 0) {
                TreeNode node = queue.pollLast();
                if (node.left != null) queue.addFirst(node.left);
                if (node.right != null) queue.addFirst(node.right);
                if (!hasSet) {
                    levelFirst = node.val;
                    hasSet = true;
                }
                queueSize--;
            }
            // 新的一层
            hasSet = false;
        }

        return levelFirst;
    }
}

代码精简：

public int findLeftMostNode(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null)
            queue.add(root.right);
        if (root.left != null)
            queue.add(root.left);
    }
    return root.val;
}

递归思路

class Solution {
    private  int MAX_DEEP = 0;   // 注意，不要使用static
    private  int RETURN_VAL = 0;
    public int findBottomLeftValue(TreeNode root) {
        // 深度最大的叶子节点就是这棵树的最左值
        getMaxDepth(root, 1);

        return RETURN_VAL;
    }

    private void getMaxDepth(TreeNode root, int depth) {
        if (root == null) return;
        // 更新
        if (depth > MAX_DEEP) { RETURN_VAL = root.val; MAX_DEEP = depth; }
        getMaxDepth(root.left, depth + 1); // 回溯，函数得到一个新的值
        getMaxDepth(root.right, depth + 1);
    }
}

public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        return findBottomLeftValue(root, 1, new int[]{0,0});
    }
    public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
        if (res[1]<depth) {res[0]=root.val;res[1]=depth;}
        if (root.left!=null) findBottomLeftValue(root.left, depth+1, res);
        if (root.right!=null) findBottomLeftValue(root.right, depth+1, res);
        return res[0];
    }
}

112. 路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        Deque<TreeNode> queue = new ArrayDeque<>();
        Deque<Integer> sum = new ArrayDeque<>();
        queue.addLast(root);
        sum.addLast(root.val);
        boolean hasPath = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.pollLast();
            int s = sum.pollLast();
            if (s == targetSum && node.left == null && node.right == null) {
                hasPath =  true;
                break;
            }

            if (node.left != null) { queue.addFirst(node.left); sum.addFirst(s + node.left.val); }
            if (node.right != null) { queue.addFirst(node.right); sum.addFirst(s + node.right.val); }
        }

        return hasPath;
    }
}

递归思路

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器 count 初始为目标和，然后每次减去遍历路径节点上的数值。如果最后 count == 0，同时到了叶子节点的话，说明找到了目标和。如果遍历到了叶子节点，count不为0，就是没找到。递归终止条件代码如下：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        return hasPath(root, targetSum);
    }

    // 递归让子树找目标值
    private boolean hasPath(TreeNode root, int targetSum) {
        // 值相等且为叶子节点，才会返回true
        if (root.val == targetSum && root.left == null && root.right == null) return true;

        // 向左、右子树继续查找目标值
        boolean l = false; 
        if (root.left != null) l =  hasPath(root.left, targetSum - root.val);
        if (l) return true;
        else if (root.right != null)  return hasPath(root.right, targetSum - root.val); 
        else return false;

    }
}

确定终止条件：

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;

        if(root.left == null && root.right == null && sum - root.val == 0) return true;

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

非递归思路

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 使用sum来记录所经过的路线的总和
        int SUM = 0;
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                path.add(cur.val);
                SUM += cur.val;
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right != null && cur.right != pre){
                cur = cur.right;
                continue;
            } 
            if (cur.left == null && cur.right == null && SUM == sum)
                // 输出结果
                res.add(new ArrayList<Integer>(path));

            pre = cur;
            stack.pop();

            // 恢复上一层栈的数据
            path.remove(path.size()-1);
            SUM -= cur.val;
            cur = null;

        }
        return res;
    }
}

113. 路径总和 II

迭代思路（后序遍历）

public static List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();

    int SUM = 0;
    TreeNode cur = root;
    TreeNode pre = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.addLast(cur);
            path.add(cur.val);
            SUM += cur.val;
            cur = cur.left;
        }
        cur = stack.peekLast();

        if (cur.right != null && cur.right != pre) {
            cur = cur.right;
            continue;
        }

        if (cur.left == null && cur.right == null && SUM == sum)
            res.add(new ArrayList<>(path));

        pre = cur;
        stack.pollLast();
        path.remove(path.size() - 1);
        // 回溯
        SUM -= cur.val;
        cur = null;

    }
    return res;
}

代码二

class Solution {
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        traversal(root, res, targetSum);
        return res;
    }

    private void traversal(TreeNode root, List<List<Integer>> res, int targetSum) {
        if (root == null) return ;
        path.add(root.val);
        if (root.left == null && root.right == null && root.val == targetSum) {
            res.add(new ArrayList<>(path));
        }

        traversal(root.left, res, targetSum - root.val);
        traversal(root.right, res, targetSum - root.val);

        path.remove(path.size() - 1);
    }
}

这段代码贴出来主要是和代码三比较。

代码三

private void traversal(TreeNode root, List<List<Integer>> res, int targetSum) {
    if (root == null) return ;
    path.add(root.val);
    if (root.left == null && root.right == null && root.val == targetSum) {
        res.add(new ArrayList<>(path));

        // #1 
        return;
    }

    // #2 判断
    if (root.left != null) {
        traversal(root.left, res, targetSum - root.val);
        path.remove(path.size() - 1);
    }
    if (root.right != null) {
        traversal(root.right, res, targetSum - root.val);
        path.remove(path.size() - 1);
    }
}

代码四

private void traversal(TreeNode root, List<List<Integer>> res, int targetSum) {
    if (root == null) return ;
    path.add(root.val);
    if (root.left == null && root.right == null && root.val == targetSum) {
        res.add(new ArrayList<>(path));
    } else {
        traversal(root.left, res, targetSum - root.val);
        traversal(root.right, res, targetSum - root.val);
    }
    // #3
    path.remove(path.size() - 1);
}

上面三段代码有不同的处理逻辑，当我们回溯操作（path.remove()）时需要递归环境进行判断。
比如当条件满足时则 return，可能需要你手动进行清理操作，因为代码不会走到 #3，这样，path 路径中就存在历史数据。
这个 else 的意思是因为 root 是叶子节点，就没有必要继续递归了，由于之前在path中添加了val，所以需要删除。

关于树的递归总结

如果需要遍历整颗树，递归函数就不能有返回值。
如果需要遍历某一条固定路线，递归函数就一定要有返回值！