【二叉樹】四種周遊（遞歸+疊代）

目錄

一、前序周遊

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;
    }
}