【二叉树】四种遍历（递归+迭代）

目录

一、前序遍历

1、递归 —— DLR

2、迭代 —— 用栈

二、中序遍历

1、递归 —— LDR

2、迭代 —— 用栈

三、后序遍历

1、递归 —— LRD

2、迭代 —— 用栈（不理解 有点难）

四、层序遍历

一、前序遍历

1、递归 —— DLR

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> v=new ArrayList<>();
        pre(root,v);
        return v;
    }

    public void pre(TreeNode root,ArrayList v)
    {
        if(root==null) return;
        v.add(root.val);
        pre(root.left,v);
        pre(root.right,v);
    }
}
           

2、迭代 —— 用栈

先把根节点入栈，输出根节点，因为先输出左子树再输出右子树，所以右子树先入栈，左子树后入栈，然后依次出栈，顺序刚好是DLR

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> v=new ArrayList<>();
        if(root==null) return v;
        Deque<TreeNode> st=new LinkedList<>();
        st.push(root);
        
        while(!st.isEmpty())
        {
            TreeNode n=st.pop();
            v.add(n.val);
            if(n.right!=null) st.push(n.right);
            if(n.left!=null) st.push(n.left);
        }
        return v;
    }
}
           

二、中序遍历

1、递归 —— LDR

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> v=new ArrayList<>();
        in(root,v);
        return v;
    }

    public void in(TreeNode root,ArrayList v)
    {
        if(root==null) return;
        in(root.left,v);
        v.add(root.val);
        in(root.right,v);
    }
}
           

2、迭代 —— 用栈

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> v=new ArrayList<>();
        if(root==null) return v;
        Deque<TreeNode> st=new LinkedList<>();
        
        while(!st.isEmpty()||root!=null)
        {
            while(root!=null)
            {
                st.push(root);
                root=root.left;
            }
            root=st.pop();
            v.add(root.val);
            root=root.right;
        }
        return v;
    }
}
           

三、后序遍历

1、递归 —— LRD

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

    public void post(TreeNode root,ArrayList v)
    {
        if(root==null) return ;
        post(root.left,v);
        post(root.right,v);
        v.add(root.val);
    }
}
           

2、迭代 —— 用栈（不理解 有点难）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> v=new ArrayList<>();
        Deque<TreeNode> st=new LinkedList<>();
        if(root==null) return v;

        TreeNode pre=null;
        while(!st.isEmpty()||root!=null)
        {
            while(root!=null)
            {
                st.push(root);
                root=root.left;
            }
            root=st.pop();
            if(root.right==null||root.right==pre)//如果右子树被访问过或右子树为空 则可以将根节点输出
            {
                v.add(root.val);
                pre=root;//标记更新
                root=null;
            }else//如果右子树没有被访问 那么将当前节点压栈 访问右子树
            {
                st.push(root);
                root=root.right;
            }
        }
        return v;
    }
}
           

四、层序遍历

用队列

根节点入队，然后将该根节点的左右孩子入队

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> v=new ArrayList<>();
        if(root==null) return v;
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty())
        {
            ArrayList<Integer> list=new ArrayList<>();
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode t=q.poll();
                list.add(t.val);
                if(t.left!=null) q.add(t.left);
                if(t.right!=null) q.add(t.right);
            }
            v.add(list);
        }
        return v;
    }
}