[Leetcode]144. 二叉树的前序遍历（扩展：二叉树的中序、后序、层序遍历）_扩展二叉树前序序列得出中序后序

144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]
1
2
3
4
5
6
7
8

二叉树定义：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
1
2
3
4
5
6
7
8
9

思路

1.前序遍历的规律为根节点-左节点-右节点，使用的是深度优先遍历，即先获取根节点，再递归左子树获取根节点，再递归右子树获取根节点，直到递归完成。使用递归法根据根节点–>左子树–>右子树的规则完成。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        helper(root, arr);
        return arr;
    }

    private void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //前序遍历的规则 根节点-->左子树-->右子树的规则
        res.add(root.val);
        helper(root.left, res);
        helper(root.right, res);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.使用迭代法完成，利用栈的先进后出特性，先将左子树向下所有的左节点加入list和栈中，直到左子节点为空，再出栈一次，并将出栈的右节点作为头节点，重复上诉步骤，直到遍历完所有节点。

    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<TreeNode>();
        TreeNode p = root;
        List<Integer> arr = new ArrayList<>();

        //当节点不为空时，将各个跟节点和左节点值放入list同时加入到栈中用于后续找到右节点
        while (p != null) {
            arr.add(p.val);
            treeNodes.push(p);
            p = p.left;
            
            while (p == null && !treeNodes.isEmpty()) {
                //当节点为空栈不为空时，从栈中pop出上一个遍历到的节点，并将其右节点作为头节点继续遍历。
                p = treeNodes.pop().right;
            }
        }


        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

扩展

1.二叉树的中序遍历

1.中序遍历的规律为左节点-根节点-右节点，使用的是深度优先遍历，即先递归左子树获取根节点，再获取根节点的，再递归右子树获取根节点，直到递归完成。使用递归法根据左子树–>根节点–>右子树的规则完成。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        helper(root, arr);
        return arr;
    }

    private void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //中序遍历的规则 左子树-->根节点-->右子树的规则
        helper(root.left, res);
        res.add(root.val);
        helper(root.right, res);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.使用迭代法完成，利用栈的先进后出特性，先遍历左子树到左叶子节点，将值全部放入栈中，然后出栈一次，将出栈的值放入list，并将其右节点作为头节点，重复上诉步骤，直到遍历完所有节点。

    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<TreeNode>();
        TreeNode p = root;
        List<Integer> arr = new ArrayList<>();
        //当节点不为空时，将各个跟节点和左节点值加入到栈中用于后续找到根节点和右节点
        while (p != null) {
            treeNodes.push(p);
            p = p.left;
            
            while (p == null && !treeNodes.isEmpty()) {
                //当节点为空栈不为空时，从栈中pop出上一个遍历到的节点，将其加入list中，并将其右节点作为头节点继续遍历。
                p = treeNodes.pop();
                arr.add(p.val);
                p = p.right;
            }
        }

        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.二叉树的后序遍历

1.后序遍历的规律为左节点-右节点-根节点，使用的是深度优先遍历，即先递归左子树获取根节点，再递归右子树获取根节点，再获取根节点的，直到递归完成。使用递归法根据左子树–>根节点–>右子树的规则完成。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        helper(root, arr);
        return arr;
    }

    private void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //后序遍历的规则 左子树-->右子树-->根节点的规则
        helper(root.left, res);
        helper(root.right, res);
        res.add(root.val);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.使用迭代法完成，利用栈的先进后出特性，先将右子树向下所有的右节点加入list和栈中，直到右子节点为空，再出栈一次，并将出栈的左节点作为头节点，重复上诉步骤，直到遍历完所有节点。此方法为反前序遍历法，因为前序的顺序为中-左-右。而这里使用相反的顺序添加到list中，使，其变成中-右-左。然后反转List，得到顺序为左-右-中。

    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<TreeNode>();
        TreeNode p = root;
        List<Integer> arr = new ArrayList<>();

        //当节点不为空时，将各个跟节点和左节点值放入list同时加入到栈中用于后续找到右节点
        while (p != null) {
        
            arr.add(0,p.val);
            treeNodes.push(p);
            p = p.right;
            
            while (p == null && !treeNodes.isEmpty()) {
                //当节点为空栈不为空时，从栈中pop出上一个遍历到的节点，并将其右节点作为头节点继续遍历。
                p = treeNodes.pop().left;
            }
        }
        //年少无知的我直接在这调用Collections的反转方法，参考大佬都用add(0,elment)方法，每次都加到0下标的位置
	    //Collections.reverse(arr);   

        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.二叉树的层序遍历

1.层序遍历，使用的是广度优先遍历。将头节点放入栈中，记录一层中有count个数，然后遍历count遍，遍历时把栈中的数依次放入一个list，依次把下一层的左右节点放入栈中。依次循环直到全部节点放入栈中且全部栈放入list中。

    public List<List<Integer>> levelOrder(TreeNode root) {
        //此题必须用队列,因为用栈时，会一边出栈一边入栈，不能保证上一层元素和下一层元素的顺序。
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }

        //queue用于放入一层的节点
        queue.add(root);
        int count = 0;
        
        while (!queue.isEmpty()) {
            //这一层中有多少个数
            count = queue.size();
            ArrayList<Integer> integers = new ArrayList<>();
            
            while (count > 0) {
                //将queue上一层中的数依次遍历加入list，并把当前的数的左右节点加入queue
                TreeNode pop = queue.poll();
                integers.add(pop.val);
                if (pop.left != null) {
                    queue.add(pop.left);
                }
                if (pop.right != null) {
                    queue.add(pop.right);
                }
                //count数记录上一层剩余的数
                count--;
            }
            lists.add(integers);
        }
        
        return lists;
    }
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