Code & Func

第71天。

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1: Input:

1
2

/
1 3

Output: 1 Example 2: Input:

Output: 7 Note: You may assume the tree (i.e., the given root node) is not NULL.

显然这可以用带高度的深度优先去做：

1
int findBottomLeftValue(TreeNode *root,int &height) {
2
    if (root == nullptr) {
3
        height = -1;
4
        return -1;
5
    }
6
    if (root->left == nullptr && root->right == nullptr)
7
        return root->val;
8
    int lefth,righth;
9
    lefth = righth = height + 1;
10
    int left = findBottomLeftValue(root->left,lefth);
11
    int right = findBottomLeftValue(root->right,righth);
12
    if (lefth >= righth) {
13
        height = lefth;
14
        return left;
15
    } else{
8 collapsed lines
16
        height = righth;
17
        return right;
18
    }
19
}
20
int findBottomLeftValue(TreeNode* root) {
21
    int h = 0;
22
    return findBottomLeftValue(root,h);
23
}

看起来就不优雅，而且很繁琐的样子,下面是dicuss中用广度优先去做的：

1
public int findLeftMostNode(TreeNode root) {
2
    Queue<TreeNode> queue = new LinkedList<>();
3
    queue.add(root);
4
    while (!queue.isEmpty()) {
5
        root = queue.poll();
6
        if (root.right != null)
7
            queue.add(root.right);
8
        if (root.left != null)
9
            queue.add(root.left);
10
    }
11
    return root.val;
12
}

以及python版本：

1
def findLeftMostNode(self, root):
2
    queue = [root]
3
    for node in queue:
4
        queue += filter(None, (node.right, node.left))
5
    return node.val