总结

1. 前缀和当参数，适合做分支总和不过节点的值会重复
2. backtrack技巧, 每当使用stringbuilder 加上一个数之前, 都要就它的长度.

3.         sum += root.val;
           path.add(root.val);
           if (root.left == null && root.right == null) {
               if (target == sum) {
                   result.add(new ArrayList<Integer>(path));
               }
               // 如果这里加上return, 那么必须backtrack
               // path.remove(path.size() - 1);
               // return;
           }
   
           helper(root.left, target, result, sum, path);
           helper(root.right, target, result, sum, path);
   
           // backtracking
           sum -= root.val;
           path.remove(path.size() - 1);
   

4. 要到叶子节点才行动

   1. 由上而下要注意 if (root.left == null && root.right == null) 注意放置的位置。 在这之前也一定要判断if(root == null)
   2. 由下而上要注意 (例子： Minimum Depth of Binary Tree) 1. if (root.left == null) 2. if (root.right == null)

5. 二叉树DFS的时候时间复杂度的计算方法是：看一下

   每个节点上处理的是复杂度 * 节点个数N

6. 根据根节点的位置， 可以知道左子树和右子树他们的起始位置和终止位置， 所以知道两个遍历顺序便能重建树

   1. 前序遍历

      1. 根， 左子树节点， 右子树节点

   2. 中序遍历

      1. 左子树节点， 根， 右子树节点

7. 3种traversal的要点：

   1. 如果是inorder traversal， 那么弹出栈的顺序是inorder
   2. 如果是preorder traversal， 那么弹出栈的顺序是preorder

   3. 弹出栈并出栈的数据进行处理后要考虑接下来把什么进栈，

      1. 比如postorder, 出栈的是左节点, 栈顶是根节点, 接下来要将右节点进栈来保证左右根顺序
      2. https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/471909/scala-interative-template-for-preorder-inorder-postorder