Algorithm__树

树的遍历——颜色标记法

我们知道垃圾回收算法中，有一种算法叫三色标记法。 即：

• 用白色表示尚未访问
• 灰色表示尚未完全访问子节点
• 黑色表示子节点全部访问

那么我们可以模仿其思想，使用双色标记法来统一三种遍历。

其核心思想如下：

• 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
• 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
• 如果遇到的节点为灰色，则将节点的值输出。

剑指 Offer 34.二叉树中和为某一定值

class Solution 
{
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> node = new ArrayList<Integer>();
        bfs(root,0,node,sum);
        return list;
    }
    public void bfs(TreeNode root,int all,List node,int sum)
    {
        if(root==null)return;
        node.add(root.val);
        all+=root.val;
        if(sum==all)//从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
        {
            list.add(new ArrayList<>(node));
            //return;如果加了return 会得不到正确的结果。因为代码提前return，导致后面的remove没有执行，影响回溯了。
        }
        bfs(root.left,all,node,sum);
        bfs(root.right,all,node,sum);
        node.remove(node.size()-1);
    }
}