数据结构与算法之对于递归的理解

获取二叉树所有双分支结点个数

题目

假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有双分支结点个数。

​

想法

1. 按照层次遍历算法²逻辑，修改判断结点入队时逻辑即可。
2. 前/中/后序遍历皆可

代码实现

非递归形式

/**
 * 统计二叉树的所有双分支结点个数。
 *
 * @param root 根节点
 * @return 二叉树的所有双分支结点个数
 */
public int numberOfFullTreeNode(TreeNode root) {
    int count = 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size-- > 0) {
            TreeNode poll = queue.poll();
            assert poll != null;
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
            if (poll.left != null && poll.right != null) {
                count++;
            }
        }
    }
    return -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

递归形式

需要重点去理解

public int numberOfFullTreeNode(TreeNode root){
    if(root!=null){
        if(root.left!=null&&root.right!=null){
            //双分支结点
            return numberOfFullTreeNode(root.left)+numberOfFullTreeNode(root.right)+1;
        }else{
            return numberOfFullTreeNode(root.left)+numberOfFullTreeNode(root.right);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11

‍ ↩︎

层次遍历算法

层次遍历算法

题目

原题：102. 二叉树的层序遍历 - 力扣（LeetCode）

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

逻辑思路

• 建立一个queue
• 先把根节点放进去，这时候找根节点的左右两个子节点
• 去掉根节点，此时queue里的元素就是下一层的所有节点
• 用for循环遍历，将结果存到一个一维向量里
• 遍历完之后再把这个一维向量存到二维向量里
• 以此类推，可以完成层序遍历
  

代码

这个题目其实就是考察BFS求最短路径问题，🤣写这篇文章的时候还不会这招。见谅啦

下列代码可优化

/**
 * 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> levelOrder(TreeNode root) {
        List> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue treeNodeQueue = new ArrayDeque<>();
        treeNodeQueue.add(root);
        List sameStorey = new ArrayList<>();
        while (!treeNodeQueue.isEmpty()) {
            //每当队列中弹出一个元素时，就需要将弹出元素子元素(左右)进行入队操作
            List temp = new ArrayList<>();
            while (!treeNodeQueue.isEmpty()) {
                TreeNode poll = treeNodeQueue.poll();
                temp.add(poll.val);
                if (poll.left != null) {
                    sameStorey.add(poll.left);
                }
                if (poll.right != null) {
                    sameStorey.add(poll.right);
                }
            }
            //将子节点加入到队列中，并清空集合
            treeNodeQueue.addAll(sameStorey);
            sameStorey.clear();
            lists.add(temp);
        }
        return lists;
    }
}
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
43
44
45