描述

404. 左叶子之和 - 力扣（Leetcode）

分析

什么是左叶子？

叶子节点中左边的。

实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.Stack;

//404. 左叶子之和

public class SumOfLeftLeaves404 {
	public static void main(String[] args){
		System.out.println(new Solution().sumOfLeftLeaves(
			MyUtils.buildTree(new Integer[]{3,9,20,null,null,15,7}))
		);
	}
}

class Solution {
    public int sumOfLeftLeaves1(TreeNode root) {
    	if (root == null) {
    		return 0;
    	}
    	int leftValue = sumOfLeftLeaves(root.left);
    	int rightValue = sumOfLeftLeaves(root.right);
    	int midValue = 0;
    	if (root.left != null && root.left.left == null && root.left.right == null) {
    		midValue = root.left.val;
    	}
    	return leftValue + rightValue + midValue;
    }
    public int sumOfLeftLeaves(TreeNode root) {
    	if (root == null) return 0;

    	int res = 0;
    	Stack<TreeNode> stack = new Stack<>();
    	stack.push(root);
    	TreeNode temp;
    	while(!stack.isEmpty()){
    		temp = stack.pop();
    		if (temp.left != null) {
    			if (temp.left.left == null && temp.left.right == null) {
    				//说明temp.left 就是左子节点
    				res += temp.left.val;
    			}
    			stack.add(temp.left);
    		}
    		if (temp.right != null) stack.add(temp.right);
    	}
    	return res;
    }
}


class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

class MyUtils {
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	public static TreeNode buildTree(Integer[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(Integer[] arr, Integer index) {
        if (index >= arr.length || arr[index] == null) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }
}

总结