【二叉树】找树左下角的值

解题思路：迭代解决，用队列实现

1.将根节点入队

2.求出二叉树深度

3.层序遍历二叉树到最大深度层数，队头结点为最底层最左边结点

int getDepth(struct TreeNode* node) {
    if(!node)
        return 0;

    int left = getDepth(node->left);
    int right = getDepth(node->right);
    return left > right ? left+1 : right+1;
}

int findBottomLeftValue(struct TreeNode* root){
    if(!root)
        return 0;
    
    int depth = getDepth(root);
    
    struct TreeNode* queue[10000];
    int queue_front = 0;
    int queue_rear = 0;
    queue[queue_rear++] = root;

    int i = 0;
    int j = 0;
		//因为根节点已入队，所以从1开始
    for(i = 1; i < depth; i++) {
        int queueLength = queue_rear - queue_front;
				//遍历同层所有结点，取出他们的左右孩子
        for(j = 0; j < queueLength; j++) {
            struct TreeNode* temp = queue[queue_front++];
            if(temp->left)
                queue[queue_rear++] = temp->left;
            if(temp->right)
                queue[queue_rear++] = temp->right;
        }
    }
    return queue[queue_front]->val;
}

改进版本：

int findBottomLeftValue(struct TreeNode* root){
    if(!root)
        return 0;
    
    struct TreeNode* queue[10000];
    int queue_front = 0;
    int queue_rear = 0;
    queue[queue_rear++] = root;

    int length = 0;
    int result = 0;
    while(length = queue_rear - queue_front) {
        int i = 0;
        for(i = 0; i < length; i++) {
            struct TreeNode* temp = queue[queue_front++];
            if(i == 0)
                result = temp->val;
            if(temp->left)
                queue[queue_rear++] = temp->left;
            if(temp->right)
                queue[queue_rear++] = temp->right;
        }
    }
    return result;
}