LeetCode: 505.left葉子節點

計算給定二叉樹的所有左葉子之和。

?

示例：

?

3

/ \

9 20

/ \

15 7

?

在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24

?

解析

我們需要找到這樣的節點

?

屬于葉子節點

屬于父節點的左子節點

方法一：用棧，dfs遍歷，用全局變量res作為累積和。遍歷的過程中傳遞該節點是否是左子節點。同時判斷左右子節點是否為None，則可以知道是不是左葉子節點。

class Solution:

????def sumOfLeftLeaves(self, root: TreeNode) -> int:

????????stack = []

????????res = 0

????????if not root:

????????????return res

????????stack.append((root, 0))

????????while len(stack) != 0:

????????????p, flag = stack.pop()

????????????if flag == 1:

????????????????if p.left == p.right == None:

????????????????????res += p.val

????????????if p.right:

????????????????stack.append((p.right, 0))

????????????if p.left:

????????????????stack.append((p.left, 1)) ???

????????return res

方法二，用遞歸遍歷。遍歷到左葉子節點則加上左葉子節點的值。

class Solution:

????def sumOfLeftLeaves(self, root: TreeNode) -> int:

????????self.res = 0

????????def walk(p):

????????????if p:

????????????????if p.left:

????????????????????if p.left.left == p.left.right == None:

????????????????????????self.res += p.left.val

????????????????????walk(p.left)

????????????????if p.right:

????????????????????walk(p.right)

????????walk(root)

????????return self.res

方法三， 仍是遞歸，沒有使用全局變量。而是使用在遞歸函數內部累積的方式（即有返回值）。遍歷到左葉子節點，則返回值就在此基礎上加上右節點的遍歷。

class Solution:

????def sumOfLeftLeaves(self, root: TreeNode) -> int:

????????if root == None:

????????????return 0

????????res = 0

????????if root.left:

????????????if root.left.left == root.left.right == None:

???????????????res += root.left.val

????????return res + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

方法四，在遞歸的過程中，用一個形參記錄該節點是否為左孩子點。和用stack遍歷類似。

class Solution:

????def sumOfLeftLeaves(self, root: TreeNode) -> int:

????????def cal(p, dir):

????????????if not p:

????????????????return 0

????????????if p.left == p.right == None:

????????????????if dir == 1:

????????????????????return p.val

????????????????else:

????????????????????pass ?????

????????????return cal(p.left, 1) + cal(p.right, 0)

????????return cal(root, 0)

?

方法五，當然還能用bfs遍歷，遍歷到左葉子節點就加上去。

/**

?* Definition for a binary tree node.

?* struct TreeNode {

?* ????int val;

?* ????TreeNode *left;

?* ????TreeNode *right;

?* ????TreeNode(int x) : val(x), left(NULL), right(NULL) {}

?* };

?*/

class Solution {

public:

????int sumOfLeftLeaves(TreeNode* root) {

????????if (!root)

????????????return 0;

????????if (root->left && !root->left->left && !root->left->right) {

????????????return root->left->val + sumOfLeftLeaves(root->right);

????????}

????????return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

????}

};

class TreeNode {

????int val;

????TreeNode left;

????TreeNode right;

?

????TreeNode(int x) {

????????val = x;

????}

}

?

class Solution {

????public int getLeafCount(TreeNode root) {

????????if (root == null) {

????????????return 0;

????????}

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

????????????// 輸出葉子節點

????????????System.out.println("leaf nodes:" + root.val);

????????????return 1;

????????}

????????return getLeafCount(root.left) + getLeafCount(root.right);

????}

}

public class Test {

????public static void main(String[] args) {

????????Solution tree = new Solution();

????????/* create a tree */

????????TreeNode root = new TreeNode(3);

????????root.left = new TreeNode(9);

????????root.right = new TreeNode(20);

????????function(){ //XM返傭 http://www.fx61.com/brokerlist/xm.html

????????root.right.left = new TreeNode(15);

????????root.right.right = new TreeNode(7);

????????System.out.println(tree.getLeafCount(root));

????}

}