day13 二叉树的遍历

一、二叉树的递归遍历

题目链接：

144.二叉树的前序遍历(opens new window)
145.二叉树的后序遍历(opens new window)
94.二叉树的中序遍历
文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF
视频讲解：https://www.bilibili.com/video/BV1Wh411S7xt

1.1 初见思路

递归三要素：入参、返回条件、单层循环逻辑

1.2 具体实现

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //前序遍历:根左右
        List<Integer> list = new ArrayList<Integer>();
        pre(root,list);
        return list;
    }
    public void pre(TreeNode node ,List<Integer> list){
        if(node==null){
            return;
        }
        list.add(node.val);
        pre(node.left,list);
        pre(node.right,list);
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //中序遍历:左根右
        List<Integer> list = new ArrayList<Integer>();
        in(root,list);
        return list;
    }
    public void in(TreeNode node ,List<Integer> list){
        if(node==null){
            return;
        }
        in(node.left,list);
        list.add(node.val);
        in(node.right,list);
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer> ();
        post(root,list);
        return list;
    }

    void post(TreeNode node,List<Integer> list){
        if(node==null){
            return;
        }
        post(node.left,list);
        post(node.right,list);
        list.add(node.val);
    }
    
}

1.3 重难点

二、二叉树的非递归遍历

题目链接：

144.二叉树的前序遍历(opens new window)
145.二叉树的后序遍历(opens new window)
94.二叉树的中序遍历
文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：
写出二叉树的非递归遍历很难么？（前序和后序）(opens new window)
写出二叉树的非递归遍历很难么？（中序）)

2.1 初见思路

非递归就是使用栈来模拟递归的操作

2.2 具体实现

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        //前序遍历：中左右
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node!=null){
                list.add(node.val);
                //栈是先进后出，所以先push右边的节点
                stack.push(node.right);
                stack.push(node.left);
            }
            
        }
        return list;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

2.3 重难点

后序遍历的入栈顺序

三、 102. 二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
文章讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1GY4y1u7b2

3.1 初见思路

使用辅助队列来实现，同时使用一个int变量来控制层数

3.2 具体实现

`class Solution {
public List<List> levelOrder(TreeNode node) {
List<List> resList = new ArrayList<List>();

   if (node == null) return resList;
    Queue<TreeNode> que = new LinkedList<TreeNode>();
    que.offer(node);

    while (!que.isEmpty()) {
        List<Integer> itemList = new ArrayList<Integer>();
        int len = que.size();

        while (len > 0) {
            TreeNode tmpNode = que.poll();
            itemList.add(tmpNode.val);

            if (tmpNode.left != null) que.offer(tmpNode.left);
            if (tmpNode.right != null) que.offer(tmpNode.right);
            len--;
        }

        resList.add(itemList);
    }
    return resList;
}

}