對于二叉樹的遍歷問題

目錄

一、二叉樹的前序遍歷

1.1遞回方法

1.2迭代方法

二、二叉樹的中序遍歷

2.1遞回方法

2.2迭代方法

三、二叉樹的后續遍歷

3.1遞回方法

3.2迭代方法

四、 二叉樹的逐層遍歷

一、二叉樹的前序遍歷

1.1遞回方法

對于前序遍歷，我們一般采取根節點——根左子樹——根右子樹的方法來進行遞回，

（1、

    void preOrderTraversal(Node root){
        if(root==null){
            return;
        }
        System.out.println(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

(2、

    //遍歷思路
    List<Integer> list=new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return list;

        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);

        return list;
    }

（3、

    //子問題思路
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;

        list.add(root.val);
        List<Integer> listleft=preorderTraversal(root.left);
        list.addAll(listleft);
        List<Integer> listright=preorderTraversal(root.right);
        list.addAll(listright);

        return list;
    }

1.2迭代方法

對于迭代來說我們會額外的加入一個堆疊，通過對于堆疊中是否有元素和元素的位置來判斷

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                list.add(cur.val);
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            cur=cur.right;
        }
        return list;
    }

二、二叉樹的中序遍歷

2.1遞回方法

對于中序遍歷，我們一般采取根左子樹——根節點——根右子樹的方法來進行遞回，

（1、

    void inOrderTraversal(Node root){
        if(root==null) return;
        inOrderTraversal(root.left);
        System.out.println(root.val);
        inOrderTraversal(root.right);
    }

（2、

    //遍歷思路
    List<Integer> list=new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null) return list;

        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);

        return list;
    }

（3、

    //子問題思路
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;
        
        List<Integer> listleft=inorderTraversal(root.left);
        list.addAll(listleft);
        list.add(root.val);
        List<Integer> listright=inorderTraversal(root.right);
        list.addAll(listright);

        return list;
    }

2.2迭代方法

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;

        Stack<TreeNode> stack=new Stack<>();
        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }

三、二叉樹的后續遍歷

3.1遞回方法

（1、

    void postOrderTraversal(Node root){
        if(root==null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.val);
    }

（2、

    //遍歷思路
    List<Integer> list=new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null) return list;

        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);

        return list;
    }

（3、

    //子問題思路
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;

        List<Integer> listleft=postorderTraversal(root.left);
        list.addAll(listleft);
        List<Integer> listright=postorderTraversal(root.right);
        list.addAll(listright);
        list.add(root.val);

        return list;
    }

3.2迭代方法

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=null;
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
            root=stack.pop();
            if(root.right==null||root.right==cur){
                list.add(root.val);
                cur=root;
                root=null;
            }else {
                stack.push(root);
                root=root.right;
            }
        }
        return list;
    }

四、 二叉樹的逐層遍歷

將二叉樹一層一層的遍歷，通過佇列來實作，

（1、

    // 層序遍歷
    void levelOrderTraversal(TreeNode root){
        if(root==null) return;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode temp=queue.poll();
            System.out.println(temp.val+" ");

            if(temp.left!=null){
                queue.offer(temp.left);
            }

            if(temp.right!=null){
                queue.offer(temp.right);
            }
        }
    }

（2、

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size=queue.size();
            List<Integer> list1=new ArrayList<>();
            while (size!=0){
                TreeNode temp=queue.poll();
                list1.add(temp.val);
                if(temp.left!=null){
                    queue.add(temp.left);
                }
                if(temp.right!=null){
                    queue.add(temp.right);
                }
                size--;
            }
            list.add(list1);
        }
        return list;
    }