求一个二叉树的最下层最左边的节点

如下图所示：

求出上述二叉树最下层最左边的节点。
我们给二叉树的每个节点加上一个层数的变量。层数为父亲节点的层数+1
#include
#include
using namespace std;
struct Node
{
int val;
int level = 0;
Node *lChild;
Node *rChild;
Node(int val,int level,Node *l = nullptr, Node *r = nullptr)
{
this->val = val;
this->lChild = l;
this->rChild = r;
this->level = level;//定义该节点的层数

}
Node()
{
this->lChild = nullptr;
this->rChild = nullptr;
}
};
Node *createTree(int intarr[], int length, int i,int level)
{
Node *root = nullptr;
if (i < length && intarr[i] != -1)
{
root = new Node(intarr[i], level);
root->lChild = createTree(intarr, length, i * 2 + 1, level+1);
root->rChild = createTree(intarr, length, i * 2 + 2, level+1);
}
return root;
}
Node *getLeftOfBottom(Node *nood)
{
queue<Node *> qnode;
int level = 0;
Node *node = nood;
qnode.push(nood);
while (!qnode.empty())
{
Node *temp = qnode.front();
if (temp->level > level)
{
level = temp->level;
node = temp;
}
qnode.pop();
if (temp->lChild)
{
qnode.push(temp->lChild);
}
if (temp->rChild)
{
qnode.push(temp->rChild);
}
}
return node;
}
int main()
{
int intarr[7] = { 3,9,20,-1,-1,15,7 };
Node *root = createTree(intarr, 7, 0,0);
Node *n = getLeftOfBottom(root);
cout << n->val << endl;
system(“pause”);
return 0;
}