CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第十五天｜二叉树层序遍历

Posted on

今天的重点是二叉树的层序遍历，思想也比较简单，分别用递归和队列实现了一下如下:

LeetCode 102.二叉树的层序遍历

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
30
31
32
33
34
35
36
37
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList();

        if (root != null) {
            recursiveLevelOrder(0, ans, root);
        }

        return ans;
    }
    // an int variable 'level' is needed to record which level a node is
    private void recursiveLevelOrder (int level, List<List<Integer>> ans, TreeNode node) {
        
        if (node == null) {
            return;
        }

        // if the list which would record this node has not been created, new one and record
        if (ans.size() <= level) {
            List<Integer> list = new LinkedList<>();
            list.add(node.val);
            ans.add(list);
        }else{
            ans.get(level).add(node.val);
        }

        // actually, no need to check if left or right is null
        if (node.left != null) {
            recursiveLevelOrder(level + 1 , ans, node.left);
        }

        if (node.right != null) {
            recursiveLevelOrder(level + 1, ans, node.right);
        }

    }
}
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
30
31
32
33
34
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList();

        if (root != null) {
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode node = root;

            queue.add(node);
            while (!queue.isEmpty()) {
                
                int size = queue.size();

                List<Integer> list = new LinkedList<>();
                for (int i = 0; i < size; i++) {
                    node = queue.poll();
                    list.add(node.val);
                    
                    if (node.left != null) {
                        queue.add(node.left);
                    }

                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                ans.add(list);
            }
        }

        return ans;
    }
   
}

LeetCode 101.对称二叉树

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
30
31
32
class Solution {
    public boolean isSymmetric(TreeNode root) {

        if (root != null) {
            return compare(root.left, root.right);
        }

        return false;

    }

    private boolean compare (TreeNode left, TreeNode right) {

        if (left == null && right != null) {
            return false;
        }else if (left != null && right == null) {
            return false;
        }else if (left == null && right == null) {
            return true;
        }

        if ( left.val != right.val) {
            return false;
        }

        boolean outsidePair = compare(left.left, right.right);
        boolean insidePair = compare(left.right, right.left);

        return outsidePair && insidePair;

    }
}

LeetCode 226.翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            reverseTree(root);
        }
        return root;
    }

    private void reverseTree(TreeNode node) {

        if (node == null) {
            return;
        }

        // swap the two nodes
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        reverseTree(node.left);
        reverseTree(node.right);

    }
}