遍历

广度优先遍历

广度优先遍历(Breadth-first-first order): 尽可能先访问距离根最近的节点，也成为层序遍历
下面为队列实现广度优先遍历

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
//二叉树层序遍历
public class E01Leetcode102 {
    /*
            1
           / \
          2   3
         / \  / \
        4  5  6  7
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        //链表没有容量限制
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        int c1 = 1;//当前节点数
        while(!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int c2 = 0; //下一层节点数
            for (int i = 0; i < c1; i++) {
                //从头部获取元素
                TreeNode n = queue.pool();
                level.add(n.val);
                if(n.left != null) {
                    queue.offer(n.left);
                    c2++;
                }
                if(n.right != null) {
                    queue.offer(n.right);
                    c2++;
                }
            }
            result.add(level);
            c1 = c2;
        }
        return result;
    }
}

深度优先遍历

深度优先遍历(Depth-first order) : 对于二叉树，可以进一步分成三种(要深入叶子节点)
1、pre-order 前序遍历，对于每一颗子树，先访问该节点，然后是左子树，最后是右子树
2、in-order 中序遍历，对于每一颗子树，先访问左子树，然后是该节点，最后是右子树
3、post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

递归实现三中深度遍历

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
/**
     * 前序遍历(递归版)
     * @param node-节点
     */
    static void preOrder(TreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }
        System.out.print(node.val + "\t"); //值
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历(递归版)
     * @param node-节点
     */
    static void inOrder(TreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }
        preOrder(node.left);
        System.out.print(node.val + "\t"); //值
        preOrder(node.right);
    }

    /**
     * 后序遍历(递归版)
     * @param node-节点
     */
    static void postOrder(TreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }
        preOrder(node.left);
        preOrder(node.right);
        System.out.print(node.val + "\t"); //值
    }

非递归实现

实现思路：前中后遍历虽然看起来不一样但是其实本质上都是从root一路走回来的过程，只不过是取值的时机不一样而已。实现走出去还要回来的数据结构选择栈，这样就可以实现三中非递归遍历，只不过代码略有差异且难想。

前序遍历：只要打印去的路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;// 代表当前节点
while(curr != null || !stack.isEmpty()) {
    if(curr != null) {
        System.out.println("去" + curr.val); // 前序遍历
        stack.push(curr);// 压入栈，为了记住回来的路
        curr = curr.left;
    } else {
        TreeNode pop = stack.pop();
        //System.out.println("回"+pop.val); // 中序遍历
        curr = pop.right;
    }
}

中序遍历：只要打印回的路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;// 代表当前节点
while(curr != null || !stack.isEmpty()) {
    if(curr != null) {
        //System.out.println("去" + curr.val); // 前序遍历
        stack.push(curr);// 压入栈，为了记住回来的路
        curr = curr.left;
    } else {
        TreeNode pop = stack.pop();
        System.out.println("回"+pop.val); // 中序遍历
        curr = pop.right;
    }
}

后序遍历：判断根节点是否需要出栈是难点，只有右子孩子遍历完之后才能弹栈到自己遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;// 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while(curr != null || !stack.isEmpty()) {
    if(curr != null) {
        System.out.println("去" + curr.val); // 前序遍历
        stack.push(curr);// 压入栈，为了记住回来的路
        curr = curr.left;
    } else {
        TreeNode peek = stack.peek();
        //后续遍历判断右孩子是否遍历完成
        if(peek.right == null || peek.right == pop) {
            pop = stack.pop();
            System.out.println("回"+pop.val); // 中序遍历
        } else {
            //右子孩子 != null
            curr = peek.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
//前中后三合一，三个愿望，一次满足！
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;// 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {
    if (curr != null) {
        stack.push(curr);// 压入栈，为了记住回来的路
        System.out.println("前" + curr.val);// 值左右，在待处理左右子树之前就取值
        //待处理左子树
        curr = curr.left;
    } else {
        TreeNode peek = stack.peek();
        //没有右子树
        if (peek.right == null) {
            System.out.println("中" + peek.val);//没有右子树可以处理那也取值
            pop = stack.pop();
            System.out.println("后" + pop.val);// 没有右子树可以处理那也取值
        }
        //右子树处理完成
        else if (peek.right == pop) {
            pop = stack.pop();
            System.out.println("后" + pop.val);// 左右子树都处理完成了就取值
        }
        //待处理右子树
        else {
            //右子孩子 != null
            System.out.println("中" + peek.val);// 左值右，在右子树处理完之前就要打印
            curr = peek.right;
        }
    }
}

二叉树经典题

力扣101-对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isSymmetric(TreeNode root) {
    return check(root.left, root.right);
}
private boolean check(TreeNode left, TreeNode right) {
    if(left == null && right == null) {
        return true;
    }
    //代码能走到这说明left和right不能同时为null
    if(right == null || left == null) {
        return false;
    }
    //值不相等一定是false
    if(left.val != right.val) {
        return false;
    }
    return check(left.left, right.right) && check(left.right, right.left);
}

力扣104-二叉树的最大深度

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
    思路：
    1、得到左子树深度，得到右子树深度，二者最大者加一，就是本节点深度
    2、因为需要先得到左右子树深度，很显然是后序遍历典型应用
    3、关于深度的定义：从根出发，离根最远的节点总边数
        注意：力扣里的深度定义要多一
 */
public int maxDepth(TreeNode root) {
    //递归
    if(root == null) {
        return 0;
    }
    return Integer.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

方法二：后序遍历

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
/*
    思路：
    1、使用非递归后序遍历，栈的最大高度即为最大深度
 */
public int maxDepth(TreeNode root) {
    TreeNode curr = root;
    TreeNode pop = null;
    LinkedList<TreeNode> stack = new LinkedList<>();
    int max = 0;// 栈的最大高度
    while(curr != null || !stack.isEmpty()) {
        if(curr != null) {
            stack.push(curr);
            int size = stack.size();
            if(size > max) {
                max = size;
            }
            curr = curr.left;
        } else {
            TreeNode peek = stack.peek();
            if(peek.right == null || peek.right == pop) {
                pop = stack.pop();
            } else {
                curr = peek.right;
            }
        }
    }
    return max;
}

方法三：层序遍历

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
/*
        思路：
        1、使用层序遍历，层数即最大深度
     */
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if(poll.left != null) {
                    queue.offer(poll.left);
                }
                if(poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            ans++;
        }
        return ans;
    }

力扣111-二叉树的最小深度

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }
    if(root.left == null && root.right == null) {
        return 1;
    }
    int p1 = minDepth(root.left);
    int p2 = minDepth(root.right);
    if(p2 == 0) { //不做加法
        return p1 + 1;
    }
    if(p1 == 0) {
        return p2 + 1;
    }
    return Math.min(p1, p2) + 1;
}

方法二：层序遍历

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
/*
    思路：
    1、遇到的第一个叶子节点就是最小深度
 */
public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int ans = 0;
    while(!queue.isEmpty()) {
        int size = queue.size();
        ans++;
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            if(poll.left == null && poll.right == null) {
                return ans;
            }
            if(poll.left != null) {
                queue.offer(poll.left);
            }
            if(poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }
    return ans;
}

力扣226-翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public TreeNode invertTree(TreeNode root) {
    //递归函数的终止条件，节点为空时返回
    if(root==null) {
        return null;
    }
    //下面三句是将当前节点的左右子树交换
    TreeNode tmp = root.right;
    root.right = root.left;
    root.left = tmp;
    //递归交换当前节点的 左子树
    invertTree(root.left);
    //递归交换当前节点的 右子树
    invertTree(root.right);
    //函数返回时就表示当前这个节点，以及它的左右子树
    //都已经交换完了
    return root;
}

后缀表达式的二叉树形式

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
static class TreeNode {
    public String val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(String val) {
        this.val = val;
    }
    public TreeNode(TreeNode left, String val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }
    @Override
    public String toString() {
        return this.val;
    }
}
public TreeNode constructExpressionTree(String[] tokens) {
    //栈
    LinkedList<TreeNode> stack = new LinkedList<>();
    for (String t : tokens) {
        if(t.equals("+")  || t.equals("-") || t.equals("*") || t.equals("/")) {
            TreeNode right = stack.pop();
            TreeNode left = stack.pop();
            TreeNode root = new TreeNode(t);
            root.left = left;
            root.right = right;
            stack.push(root);
        }
        else {
            //是数字就直接压入栈
            stack.push(new TreeNode(t));
        }
    }
    return stack.peek();
}