4/25剑指offer

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;
    }
};