随意随想

知其然，知其所以然

0%

有点意思的算法题

发表于 更新于

说点题外话~

偶然一天，有个童鞋问了我这么一道题?

给你一棵二叉树，请你返回层数最深的叶子节点的和

刚开始看到这题的时候，其实没啥思路，虽然搬砖多年，但是对于算法方面的积累，估计就除了大学时候的算法结构课外，其他时间甚少接触。但是一向求(xi)知(huan)心(zhuang)切(bi)的我来说，立马就打开笔记本，刷刷刷搞起来

正题

建立好基本

既然涉及树，那么不妨先建颗 树

1
2
3
4
5
6
7
8
public class TreeNode {
    //节点的值
    public Integer val;
    //左节点
    public TreeNode left;
    //右节点
    public TreeNode right;
}

树是由多个节点构成的，节点的属性相当简单，除了有本节点的值外，还有左节点，右节点（确实有点像树杈）。如上图一目了然，现在结构有了，当然想要初始化一颗树 二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//将数组转化为树
//二叉树最为有意思的地方是，每个节点最多有两个分支
//而且左节点的index必须要是当前index*2+1，右节点index = 当前index*2+2
public static TreeNode arrayToTreeNode(Integer[] arrays) {
    if (arrays == null || arrays.length == 0) {
        return null;
    }
    List<TreeNode> nodeList = new ArrayList<>();
    for (Integer array : arrays) {
        nodeList.add(new TreeNode(array));
    }

    for (int i = 0; i < nodeList.size() / 2; i++) {
        if (i * 2 + 1 < nodeList.size()) {
            nodeList.get(i).left = nodeList.get(i * 2 + 1);
        }
        if (i * 2 + 2 < nodeList.size()) {
            nodeList.get(i).right = nodeList.get(i * 2 + 2);
        }
    }
    return nodeList.get(0);
}

树的初始化已经完成，但是我又想要输出每个节点的值，看下是否有异常，于是脑海里想到 前序遍历

1
2
3
4
5
6
7
8
9
10
11
/**
* 前序遍历
*/
public static void preLoad(TreeNode root) {
    if (root != null) {
        System.out.print(root.val);
        System.out.print(",");
        preLoad(root.left);
        preLoad(root.right);
    }
}

有前序遍历、当然少不了中序遍历、后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 中序遍历
*/
public static void midLoad(TreeNode root) {
    if (root != null) {
        preLoad(root.left);
        System.out.print(root.val);
        System.out.print(",");
        preLoad(root.right);
    }
}

/**
* 后序遍历
*/
public static void postLoad(TreeNode root) {
    if (root != null) {
        preLoad(root.left);
        preLoad(root.right);
        System.out.print(root.val);
        System.out.print(",");
    }
}

上说所说其实都是深度遍历 dfs 其实还有广度遍历 bfs 更多知识请参考 树的遍历

正解部分

解法1

最先想到的是深度排序，设定公共变量最大层数highmax,遍历叶子节点，如果当前叶子节点的层数等于highmax，则作sum运算，如果当前叶子节点层数大于highmax 则将值赋给sum，并重置目前最大层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int higtMax = -1;
int sum = 0;

public int dfsMain(TreeNode root) {
    higtMax = -1;
    sum = 0;
    dfs(root, 0);
    return sum;
}

//写法上有点类似前序遍历
public void dfs(TreeNode root, int high) {
    if (root != null && root.val != null) {
        if (high == higtMax) {
            sum += root.val;
        }
        if (high > higtMax) {
            higtMax = high;
            sum = root.val;
        }
        dfs(root.left, high + 1);
        dfs(root.right, high + 1);
    }
}

思考下，为什么要先判断等于再判断大于？

解法2

这里其实就是广度遍历,使用队列最先想到 FIFO，从左到右遍历树，一层一层遍历下去，每一层遍历完之后判断队列是否空，如果空，则达到最深层，直接返回该层叶子点数相加之和即可

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
/**
* 使用队列解答这题
*/
public static int queue(TreeNode root) {
    Queue<TreeNode> treeNodes = new LinkedList<>();
    treeNodes.add(root);
    int allSum = 0;
    while (!treeNodes.isEmpty()) {
        int size = treeNodes.size();
        int sum = 0;
        //这个for主要是统计该层的节点值
        for (int i = 0; i < size; i++) {
            TreeNode poll = treeNodes.poll();
            if (poll == null || poll.val == null) {
                continue;
            }
            sum += poll.val;
            if (poll.left != null) treeNodes.add(poll.left);
            if (poll.right != null) treeNodes.add(poll.right);
        }
        allSum = sum;
    }
    //队列为空，即可返回
    return allSum;
}

写在最后

看起来简简单单的一道算法题，却花了我不少时间，又敲代码又调试啥的，其实最主要的原因还是平时积累少，思考少。不过，不管怎么样都好，作为自己的第一篇blog，算是在机缘巧合之中，又冥冥中带有一滴滴的缘分吧。