java二叉樹(shù)的遍歷方式詳解

更新時(shí)間：2021年08月16日 09:48:12 作者：caiyec

這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)二叉樹(shù)遍歷的四種方式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能給你帶來(lái)幫助

一、前序遍歷（遞歸和非遞歸）

前序遍歷就是先遍歷根再遍歷左之后是右根左右

遞歸實(shí)現(xiàn)：

 public List<Integer> preorderTraversal(TreeNode root) {
       List <Integer>  list=new ArrayList<>();
       pre(root,list);
       return list;
    }
    public void pre(TreeNode root,List list){
        if(root==null){
            return ;
        }
        list.add(root.val);
        pre(root.left,list);
        pre(root.right,list);
    }

迭代實(shí)現(xiàn)：

利用棧來(lái)實(shí)現(xiàn) 先將樹(shù)的右子樹(shù)放入棧中，再放入左子樹(shù)

 public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;
        Stack<TreeNode>  stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            list.add(node.val);
           if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }
        return list;
    }

二、中序遍歷（遞歸和非遞歸）

中序遍歷就是先遍歷左再遍歷根，最后遍歷右左根右

遞歸實(shí)現(xiàn)：

 public List<Integer> inorderTraversal(TreeNode root) {
         List <Integer> list=new ArrayList<>();
         inorder(root,list);
         return list;
    }
    public void inorder(TreeNode root,List list){
        if(root==null){
            return ;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

迭代實(shí)現(xiàn)

利用棧來(lái)實(shí)現(xiàn)，二叉樹(shù)的中序遍歷，由于中序遍歷是左根右，先定義節(jié)點(diǎn)找到最左節(jié)點(diǎn)入棧，之后出棧，判斷該節(jié)點(diǎn)是否有右孩子

 public List<Integer> inorderTraversal(TreeNode root) {
        //迭代實(shí)現(xiàn) 
        List<Integer> list =new LinkedList<>();
        Stack <TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            //先找到左節(jié)點(diǎn)
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode node=stack.pop();
            list.add(node.val);
            if(node.right!=null){
              cur=node.right;
            }
        }
        return list;
    }

三、后序遍歷（遞歸和非遞歸）

后序遍歷就是左右根

遞歸實(shí)現(xiàn)：

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
            postorder(root,list);
            return list;
    }
    public void postorder(TreeNode root,List list){
        if(root==null){
            return ;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }

非遞歸實(shí)現(xiàn)：

用兩個(gè)棧來(lái)實(shí)現(xiàn)二叉樹(shù)的后序遍歷

第一個(gè)棧先放入根節(jié)點(diǎn)，之后彈出放入第二個(gè)節(jié)點(diǎn)，之后第一個(gè)棧放入左右孩子，之后再?gòu)棾龇湃氲诙€(gè)棧，即可實(shí)現(xiàn)

 public List<Integer> postorderTraversal(TreeNode root) {
        //利用雙棧實(shí)現(xiàn)后序遍歷
        Stack <TreeNode> s1=new Stack<>();
        Stack <TreeNode> s2=new Stack<>();
        List<Integer> list=new LinkedList<>();
          if(root==null) return list;
        s1.push(root);
        while(!s1.isEmpty()){
            TreeNode node=s1.pop();
            s2.push(node);
            if(node.left!=null) s1.push(node.left);
            if(node.right!=null) s1.push(node.right);
        }
        while(!s2.isEmpty()){
            TreeNode cur=s2.pop();
            list.add(cur.val);
        }
        return list;
    }

四、層序遍歷

用隊(duì)列實(shí)現(xiàn)層序遍歷

public List<List<Integer>> levelOrder(TreeNode root) {
        //用隊(duì)列實(shí)現(xiàn)層序遍歷
        //第一層節(jié)點(diǎn)先進(jìn)隊(duì)列，出的節(jié)點(diǎn)帶下一層的節(jié)點(diǎn)
        List <List<Integer>> list=new ArrayList<>();
         if(root==null) return list;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list1=new ArrayList<>();
            int size=queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                list1.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(list1);
        }
        return list;
    }