1.题目描述
给定一棵完全二叉树，返回最后一层的最右边的节点。
2.思路分析
层次遍历，输出最后一个节点，时间复杂度：O(N)
递归，求子树的高度：如果左子树高度>右子树高度，则在左子树继续递归过程；否则在右子树继续递归。如果当前节点为叶子节点，则返回；由于是完全二叉树，求高度时只需一直往左遍历即可。每次递归都下降一层，每次都求树的高度，时间复杂度为O(lgN * lgN)。
3.代码实现
/*
* 递归
* 求子树高度：如果当前根节点为叶子节点，则返回
* 如果左子树高度>右子树高度，则在左子树递归
* 否则在右子树递归
* 时间复杂度O(logN * logN) （求高度 * 遍历层数）
*/
class Solution {
public:
TreeNode* getLastNode(TreeNode* root) {
// 递归出口
if(!root || root->left == nullptr)
return root;
int leftHeight = 0; // 左子树高度
TreeNode *node = root->left;
while (node){
node = node->left;
++ leftHeight;
}
int rightHeight = 0; // 右子树高度
node = root->right;
while(node){
// 从左孩子开始计算高度
node = node->left;
++ rightHeight;
}
if(leftHeight > rightHeight)
return getLastNode(root->left);
else
// 相等时也是在右子树递归
return getLastNode(root->right);
}
};
