LeetCode题目——左叶子之和(sum-of-left-leaves)

计算给定二叉树的所有左叶子之和。

示例：

    3

   / \

  9  20

    /  \

   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

思路

本题的难点在于，首先要知道

什么是叶子节点 ?
如何判断一个节点是不是左叶子节点 ?

第一个问题，

如果一个节点没有左右孩子，那么这个节点就是叶子节点。或者一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。

我们看一下节点的代码TreeNode，如下

public class TreeNode {

	public int val;

	public TreeNode left;

	public TreeNode right;

	public TreeNode(int x) {

		val = x;

	}

}

很明显节点自己就可以判断它的左右孩子是不是空。

第二个问题,

如何判断一个节点是不是左叶子节点，这个只能由它的父亲来判断。

深圳优先搜索

package sum_of_left_leaves;

import common.TreeNode;

//404. 左叶子之和

public class Solution {

    public int sumOfLeftLeaves(TreeNode root) {

        return root != null ? dfs(root) : 0;

    }

    //深度优先搜索

    public int dfs(TreeNode node) {

        int ans = 0;

        if (node.left != null) {

            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);

        }

        //当前节点的右节点不为空，并且不是叶子节点，则继续进行深度优先搜索

        if (node.right != null && !isLeafNode(node.right)) {

            ans += dfs(node.right);

        }

        return ans;

    }

    //判断是否是叶子节点

    public boolean isLeafNode(TreeNode node) {

        return node.left == null && node.right == null;

    }

	public static void main(String[] args) {

		TreeNode root = new TreeNode(3);

		TreeNode root_l = new TreeNode(9);

		TreeNode root_r = new TreeNode(20);

		TreeNode root_rl = new TreeNode(15);

		TreeNode root_rr = new TreeNode(7);

		root.left = root_l;

		root.right = root_r;

		root_r.left = root_rl;

		root_r.right = root_rr;

		Solution s =new Solution();

		int sum = s.sumOfLeftLeaves(root);

		System.out.println(sum);

	}

}

广度优先搜索

package sum_of_left_leaves;

import java.util.LinkedList;

import java.util.Queue;

import common.TreeNode;

class Solution2 {

    public int sumOfLeftLeaves(TreeNode root) {

        if (root == null) {

            return 0;

        }

        //定义一个队列，把一层的数据添加到队列中。

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);

        int ans = 0;

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            if (node.left != null) {

                if (isLeafNode(node.left)) {

                    ans += node.left.val;

                } else {

                    queue.offer(node.left);

                }

            }

            if (node.right != null) {

                if (!isLeafNode(node.right)) {

                    queue.offer(node.right);

                }

            }

        }

        return ans;

    }

    //判断当前节点是否是叶子节点

    public boolean isLeafNode(TreeNode node) {

        return node.left == null && node.right == null;

    }

}

测试数据

	public static void main(String[] args) {

		TreeNode root = new TreeNode(3);

		TreeNode root_l = new TreeNode(9);

		TreeNode root_r = new TreeNode(20);

		TreeNode root_rl = new TreeNode(15);

		TreeNode root_rr = new TreeNode(7);

		root.left = root_l;

		root.right = root_r;

		root_r.left = root_rl;

		root_r.right = root_rr;

		Solution s =new Solution();

		int sum = s.sumOfLeftLeaves(root);

		System.out.println(sum);

	}

输出24

一个函数

可以看到，上面的代码都是用了三个函数，那可以用一个函数搞定吗。也是可以的。

class Solution {

    public int sumOfLeftLeaves(TreeNode root) {

        if (root == null) return 0;

        int sum = 0;

        if (root.left != null && root.left.left == root.left.right) {

            sum = root.left.val;

        }

        return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);

    }

}

TreeNode树节点的代码

package common;

import java.util.LinkedList;

import java.util.Queue;

public class TreeNode {

	public int val;

	public TreeNode left;

	public TreeNode right;

	public TreeNode(int x) {

		val = x;

	}

}

巴特西

左叶子之和(sum-of-left-leaves)