遍历

递归序

1
2
3
4
5
6
7
8
void process(Node root){
    if(root == null) return;
    //第一次到达root
    process(root.left);
    //第二次到达root
    process(root.right);
    //第三次到达root
}

在递归序中，每个节点都会被经过3次，这就意味着二叉树递归遍历时，可以从左子树收集一些信息，再从右子树收集一些信息，然后返回头节点，完成信息的整合

非递归

显然需要回溯，所以要用到压栈的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void process(Node root){
    Stack<Node> s = new Stack<>();
    while(root != null || !s.isEmpty()){
        while(root != null){
            s.push(root);
            //先序
            root = root.left;
        }
        Node cur = s.pop();
        //中序
        root = root.right;
    }
}

//后序就是头->右->左，然后反转
void process(Node root){
    Stack<Node> s = new Stack<>();
    while(root != null || !s.isEmpty()){
        while(root != null){
            s.push(root);
            //后序
            root = root.right;
        }
        Node cur = s.pop();
        root = root.left;
    }
}

按层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void byLevel(Node head){
    Queue<Node> nodes = new LinkedList<>();
    nodes.add(head);
    while(!nodes.isEmpty()){
        head = nodes.poll();
        //System.out.println(head.value);
        if(head.left != null){
            nodes.add(head.left);
        }
        if(head.right != null){
            nodes.add(head.right);
        }
    }
}

最大宽度（怎么发现层的结束）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//用HashMap
int byLevel(Node head){
    if(head == null) return 0;
    Queue<Node> nodes = new LinkedList<>();
    nodes.add(head);
    HashMap<Node, Integer> m = new HashMap<>();
    m.put(head, 1);//head在第一层
    int max = 0;
    int level = 1; //统计到第几层了
    int count = 0; //当前层的宽度
    while(!nodes.isEmpty()){
        Node cur = nodes.poll();
        int curLevel = m.get(cur);
        if(cur.left != null){
            m.put(cur.left, curLevel + 1);
            nodes.add(cur.left);
        }
        if(cur.right != null){
            m.put(cur.right, curLevel + 1);
            nodes.add(cur.right);
        }
        
        if(curLevel == level){
            count++;
        }else{
            max = Math.max(max, count);
            level++;
            count = 1;
        }
    }
    return Math.max(max, count);
}

//不用HashMap
int byLevel(Node head){
    if(head == null) return 0;
    Queue<Node> nodes = new LinkedList<>();
    nodes.add(head);
    Node curEnd = head;//当前层最右边的节点
    Node nextEnd = null;//下一层最右边的节点
    int max = 0;
    int count = 0; //当前层的宽度
    while(!nodes.isEmpty()){
        Node cur = nodes.poll();
        if(head.left != null){
            nodes.add(head.left);
            nextEnd = cur.left;
        }
        if(head.right != null){
            nodes.add(head.right);
            nextEnd = cur.right;
        }
        count++;
        if(cur == curEnd){
            max = Math.max(max, count);
            count = 0;
            curEnd = nextEnd;
        }
    }
    return max;
}

树形DP

本质是利用递归遍历二叉树的便利性

  1. 假设以X节点为头，假设可以向X左树和X右树要任何信息
  2. 在上一步的假设下，讨论以X为头节点的树，得到答案的可能性
  3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
  4. 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
  5. 递归函数都返回S，每一棵子树都这么要求
  6. 写代码，在代码中考虑如何吧左树的信息和右树的信息整合出整棵树的信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TreeDP{
    //信息
    class Info{
        //定义一些需要收集的信息
        //a
        //b
        public Info(a,b){
            this.a = a;
            this.b = b;
        }
    }
    //节点
    class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }
	//入口
    xxx method(Node root){
        return process(root).a;
        //或者
        return process(root).b;
    }
    //用递归的方式整合信息
    Info process(Node cur){
        if(cur == null) return new Info(xxx,xxx);
        Info leftInfo = process(cur.left);
        Info rightInfo = process(cue.right);
        //此处整合Info
        a = xxxx;
        b = xxxx;
        return new Info(a,b);
    }
}