1.二叉搜索树的第k大节点
思路:中序遍历的二叉搜索树是一个递增序列。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: TreeNode* KthNode(TreeNode* pRoot, int k) { if(pRoot==nullptr||k==0) return nullptr; return KthNodeCore(pRoot,k); } TreeNode* KthNodeCore(TreeNode* pRoot,int &k) { TreeNode* target=nullptr; //中序遍历 if(pRoot->left) { target=KthNodeCore(pRoot->left,k);//先遍历左子树 } if(target==nullptr)//左子树中没找到 { if(k==1) target=pRoot;//左子树为空,k=1,返回根节点 k--;//否则,记遍历了根节点,k-- } if(target==nullptr&&pRoot->right!=nullptr) { target=KthNodeCore(pRoot->right,k);//遍历右子树 } return target; } };
2.二叉树的深度
问题一:输入一棵二叉树的根节点,求该树的深度。
思路:分别递归求左右子树的深度,树的深度等于二者最大值+1.
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: int TreeDepth(TreeNode* pRoot) { if(pRoot==nullptr) return 0; int count=0; int left=TreeDepth(pRoot->left); int right=TreeDepth(pRoot->right); count=(left>right)?left+1:right+1; return count; } };
问题二:判断是否是平衡二叉树(某二叉树任意节点的左右子树的深度相差不超过1,即为平衡二叉树)
思路:(1)基于问题一,依次遍历每个节点,分别求其左右子树的深度做比较。
bool IsBalanced_Solution(TreeNode* pRoot) { /*遍历每个结点,借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡, 然后递归地对左右子树进行判断。 if(pRoot==NULL) return true; int left=TreeDepth(pRoot->left);//左子树最大深度 int right=TreeDepth(pRoot->right);//右子树最大深度 if(abs(left-right)>1) return false;//差大于1,不平衡 return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right); } int TreeDepth(TreeNode *p) { if(p==NULL) return 0; int left=TreeDepth(p->left);//有的话,递归遍历左子树 int right=TreeDepth(p->right);//有的话,递归遍历右子树 return left>right?left+1:right+1;//返回最大值+1 }*/
(2)利用后序遍历的方式遍历整个二叉树,在遍历完某节点的左、右子节点之后,可以根据左右子节点的深度判断其是不是平衡的,并得到当前节点的深度。但最后遍历到根节点时,也就判断了整棵树是不是平衡二叉树。
class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { int depth=0; return IsBalanced(pRoot,&depth); } bool IsBalanced(TreeNode* pRoot,int* pDepth) { if(pRoot==nullptr) { *pDepth=0; return true; } int left,right; if(IsBalanced(pRoot->left,&left)&&IsBalanced(pRoot->right,&right)) { if(abs(left-right)<=1) { *pDepth=1+(left>right?left:right); return true; } } return false; } };