树的【前序遍历】【中序遍历】【后序遍历】【层遍历】【BFS】【DFS】

leetcode

二叉树的数据结构

1
2
3
4
5
6
7
8
public static class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { 
            val = x;
        }
   }

1.二叉树的前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
//执行用时 :1 ms, 在所有 Java 提交中击败了99.62%的用户
//内存消耗 :35.1 MB, 在所有 Java 提交中击败了40.72%的用户
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root!=null){
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**依次将每层的结点入栈，入栈顺序是右--左，方便弹出时出栈为左---右**/
     //执行用时 :3 ms, 在所有 Java 提交中击败了6.05%的用户
    //内存消耗 :35 MB, 在所有 Java 提交中击败了40.72%的用户
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            //入栈下一层的右节点
            if(node.right!=null){
                stack.push(node.right);
            }
            //入栈下一层的左节点
            if(node.left!=null){
                stack.push(node.left);
            }
            //加入根节点
            res.add(node.val);
        }
        return res;
    }

2.二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//执行用时 :1 ms, 在所有 Java 提交中击败了99.55%的用户
//内存消耗 :34.7 MB, 在所有 Java 提交中击败39.5的用户
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null)
            return res;
        if(root.left!=null)
            inorderTraversal(root.left);
        res.add(root.val);
        if(root.right!=null)
              inorderTraversal(root.right);
        return res;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//执行用时 :2 ms, 在所有 Java 提交中击败了55.11%的用户
//内存消耗 :35.1 MB, 在所有 Java 提交中击败了39.36%的用户
public static List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur!=null ||!stack.isEmpty()){
                //循环直到找到最左子树
                while (cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                ans.add(cur.val);
                cur = cur.right;
            }
            return ans;
        }

3. 二叉树的后序遍历

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//执行用时 :1 ms, 在所有 Java 提交中击败了99.71%的用户
//内存消耗 :35.6 MB, 在所有 Java 提交中击败了36.80%的用户
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null)
            return res;
        if(root.left !=null)
            postorderTraversal(root.left);
         if(root.right !=null)
            postorderTraversal(root.right);
        if(root!=null)
            res.add(root.val);
        return res;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//执行用时 :2 ms, 在所有 Java 提交中击败了61.53%的用户
//内存消耗 :35.8 MB, 在所有 Java 提交中击败了35.50%的用户
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
      return res;
    }
    //这里先加入根结点
    stack.addLast(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      //在res的头部添加，依次添加的为 根，然后再添加为 右--根，再添加为左--右--根
      res.addFirst(node.val);  
      //在stack中依次加入左--右，方便下次先弹出右子树，再弹出左子树
      if (node.left != null) {
        stack.addLast(node.left);
      }
      if (node.right != null) {
        stack.addLast(node.right);
      }
    }
    return res;
    }

4.二叉树的层序遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//执行用时 :2 ms, 在所有 Java 提交中击败了90.77%的用户
//内存消耗 :37 MB, 在所有 Java 提交中击败了43.02%的用户
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return ans;
        helper(root,0);
        return ans;
    }

    private void helper(TreeNode root, int level) {
        if(ans.size() == level)
            ans.add(new ArrayList<>());

        ans.get(level).add(root.val);
        if(root.left != null)
            helper(root.left,level+1);
        if(root.right != null)
            helper(root.right,level+1);
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//执行用时 :3 ms, 在所有 Java 提交中击败了58.74%的用户
//内存消耗 :36.7 MB, 在所有 Java 提交中击败了43.83%的用户
public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //用于存一层的结果
           ArrayList<Integer> tmp = new ArrayList<>();
           //这一层的结点个数
           int count = queue.size();
           for(int i = 0; i<count;i++){
               TreeNode node = queue.poll();
               //存入下一层的左右子树
               if(node.left!=null)
                   queue.add(node.left);
               if(node.right!=null)
                   queue.add(node.right);
               //添加当前层的值到tmp    
               tmp.add(node.val);
           }
           //将一层的结果存到结果集中
           res.add(tmp);
        }
    return res;
    }

5.二叉树的深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
//递归实现
class solution{
       ArrayList<Integer> ans = new ArrayList();
       public static ArrayList<Integer> DFS(TreeNode root) {
           if (root != null) {
               ans.add(root.val);
               DFS(root.left);
               DFS(root.right);
           }
           return ans;
       }
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static ArrayList<Integer> DFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            //先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
            if(node.right!=null)
                stack.push(node.right);
            if(node.left!=null)
                stack.push(node.left);
            res.add(node.val);
        }
        return res;
    }

6.二叉树的广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static ArrayList<Integer> BFS(TreeNode root) {
         ArrayList<Integer> res = new ArrayList<>();
         if(root == null)
             return res;
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while (!queue.isEmpty()){
             TreeNode node = queue.poll();
             ////先往queue中压入左节点，再压右节点。
             if(node.left!=null)
                 queue.add(node.left);
             if(node.right!=null)
                 queue.add(node.right);
             res.add(node.val);
         }
         return res;
       }
   }

N叉树的数据结构

1
2
3
4
5
6
7
8
9
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
}

1. N叉树的前序遍历

https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//执行用时 :3 ms, 在所有 Java 提交中击败了88.62%的用户
//内存消耗 :52.2 MB, 在所有 Java 提交中击败了78.78%的用户
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root == null){
            return res;
        }
        //添加根
        res.add(root.val);
        //递归孩子结点
        for(Node node:root.children){
            preorder(node);
        }
        return res;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//执行用时 :8 ms, 在所有 Java 提交中击败了28.21%的用户
//内存消耗 :54.5 MB, 在所有 Java 提交中击败了64.22%的用户
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
       Stack<Node> stack= new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            if(node.children.size() > 0){
                //stack从右到左入栈，以达到弹出先弹左子树再弹右子树
                for(int i = node.children.size()-1;i>=0;i--){
                    stack.add(node.children.get(i));
                }
            }
        }
        return res;
    }

2. N叉树的中序遍历

    没找到相关题，略过~~~

3. N叉树的后序遍历

https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//执行用时 :3 ms, 在所有 Java 提交中击败了90.67%的用户
//内存消耗 :58.9 MB, 在所有 Java 提交中击败了25.73%的用户
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> postorder(Node root) {
        if(root == null)
            return res;
        for(Node node : root.children){
            postorder(node);
        }
        res.add(root.val);
        return res;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> postorder(Node root) {
        LinkedList<Node> stack = new LinkedList();
        LinkedList<Integer> res = new LinkedList();
        if(root == null)
            return res;

        stack.addLast(root);
        while (!stack.isEmpty()){
            Node node = stack.pollLast();
           //在res的头部添加，依次添加的为 根，然后再添加为 右--根，再添加为左--右--根
            res.addFirst(node.val);
            //判断是否有孩子结点
            if(node.children.size()>0){
                //从左到右依次入栈，方便后面先取出右子树
                for(int i = 0;i<node.children.size();i++){
                    stack.addLast(node.children.get(i));
                }
            }
        }
        return res;
    }

4. N叉树的层序遍历

https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//执行用时 :3 ms, 在所有 Java 提交中击败了98.57%的用户
//内存消耗 :58.8 MB, 在所有 Java 提交中击败了40.01%的用户
class Solution{
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null)
            return res;
        helper(root,0);
        return res;
    }

    private void helper(Node root, int level) {
        if(res.size() == level)
            res.add(new ArrayList<>());
        res.get(level).add(root.val);
        if(root.children.size()>0){
            for(Node node : root.children)
                 helper(node,level+1);
        }
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//执行用时 :7 ms, 在所有 Java 提交中击败了64.89的用户
    //内存消耗 :52.6 MB, 在所有 Java 提交中击败了79.34%的用户
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //用于存上一层的结果
            ArrayList<Integer> tmp = new ArrayList<>();
            //这一层的结点个数
            int count = queue.size();
            for(int i = 0;i<count;i++){
                Node node = queue.poll();
                //添加当前层的值到tmp    
                tmp.add(node.val);
                //存入下一层的孩子
                if(node.children.size()>0){
                    for(int j = 0;j<node.children.size();j++){
                        queue.add(node.children.get(j));
                    }
                }
            }
            //将一层的结果存到结果集中
            res.add(tmp);
        }
        return res;
    }

本文标题:树的【前序遍历】【中序遍历】【后序遍历】【层遍历】【BFS】【DFS】

文章作者:qiulig

发布时间:2019-07-26, 21:08:30

最后更新:2019-07-26, 21:20:53

文章字数:2.3k

原始链接:http://blogs.qiulig.website/2019/07/树的【前序遍历】【中序遍历】【后序遍历】【层遍历】【BFS】【DFS】/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 二叉树的数据结构
  2. 2. 1.二叉树的前序遍历
  3. 3. 2.二叉树的中序遍历
  4. 4. 3. 二叉树的后序遍历
  5. 5. 4.二叉树的层序遍历
  6. 6. 5.二叉树的深度优先遍历
  7. 7. 6.二叉树的广度优先遍历
  • N叉树的数据结构
    1. 1. 1. N叉树的前序遍历
    2. 2. 2. N叉树的中序遍历
    3. 3. 3. N叉树的后序遍历
    4. 4. 4. N叉树的层序遍历
    • | 139.6k