二叉搜索树的第K大节点

二叉搜索树的第K大节点

第K大的节点就是中序遍历中的第K个节点

class Solution:
    # 返回对应节点TreeNode
    res = 0
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot:
            return
        left = self.KthNode(pRoot.left, k)
        if left:
            return left        
        self.res += 1
        if self.res == k:
            return pRoot
        right = self.KthNode(pRoot.right, k)
        if right:
            return right

二叉树的深度

比较左边路径和右边路径哪边最长，选择最长的一边路径，加上root结点本身的长度。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }
}

平衡二叉树

判断二叉树最大深度的函数，左子树和右子树的深度差小于等于1即为平衡二叉树

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        if(Math.abs(height(root.left)-height(root.right))>1)
            return false;
        else
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    public int height(TreeNode root){
        if(root == null)
            return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
}