java数据结构与算法——二叉树面试题

一 : 二叉树的层序遍历

链接 : 二叉树的层序遍历

1.题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

2.解题

2.1思路分析

根据输出结果 , 最后要求返回的是一个二维数组 . 这个二维数组的每个元素都是一个一维数组 , 每个一维数组中存储的是该层所有节点的val值 . 我们的思路是 , 借助队列 , 具体步骤如下 :

1.创建一个二维List,存储所有的节点val值;
2.创建一个队列,存储二叉树的节点;
3.创建遍历size,存储每一行中节点的个数;
4.根节点入队;
5.根节点入队列;
6.如果队列不为空,进入循环;
7.size存储当前队列中的元素个数;创建一个List,用于存放该层所有节点的val值;
8.如果size != 0 ,进入循环 , 弹出队头元素并用新节点cur接收,将cur的val值放入队列中,同时size–,表示该层一个元素的val值已经被放入List中;
9.cur节点的左右节点,依次入队(如果存在);
10.直到size == 0 ,说明该层所有节点的val值已经被加入到List中,将该List放入二维List中;
11.直到队列为空,说明所有的节点val值已经被加入到二维List中,返回二维List.

2.2代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;

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

        while (!queue.isEmpty()) {
            int size = queue.size();//size中存储的是每一行的节点的个数
            List<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}
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
38
39
40
41
42

二 : 二叉树的完全性验证

链接 : 判断一棵树是否为完全二叉树

1.题目

给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

2.题解

2.1思路分析

方法一 : 借助层序遍历 .

2.2代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
          if(root == null) return false;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if(cur != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } else {
                    break;
                }
            }  

            while(!queue.isEmpty()){
                TreeNode cur = queue.peek();
                if(cur == null){
                    queue.poll();
                } else {
                    return false; 
                } 
            }

            return true;
    }
}
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
38
39
40
41
42

方法二 : 答案参考----广度优先搜索

借助顺序表 , 空间点不入顺序表 , 最后根据下标连续性进行判断 .

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        List<ANode> nodes = new ArrayList();
        nodes.add(new ANode(root, 1));
        int i = 0;
        while (i < nodes.size()) {
            ANode anode = nodes.get(i++);
            if (anode.node != null) {
                nodes.add(new ANode(anode.node.left, anode.code * 2));
                nodes.add(new ANode(anode.node.right, anode.code * 2 + 1));
            }
        }

        return nodes.get(i-1).code == nodes.size();
    }
}

class ANode {  // Annotated Node
    TreeNode node;
    int code;
    ANode(TreeNode node, int code) {
        this.node = node;
        this.code = code;
    }
}
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