二叉树刷题

二叉树

题目1：94 · 二叉树中的最大路径和 - LintCode

class Solution {
public:
	//求出从根到任意位置的最大长度
    int dfs(TreeNode* root,int& maxsum)
    {
	    if(root==NULL)	return 0;
	    int left=0,right=0,tmp=root->val;
	    //如果左子树存在，求出目前结点的左子树的最大长度
	    if(root->left)	left=dfs(root->left,maxsum);
	    //如果右子树存在，求出目前结点的右子树的最大长度
	    if(root->right) right=dfs(root->right,maxsum);
	    //如果左子树的最大长度是大于0的，目前结点的大小加上左子树最大长度
	    if(left>0)	tmp+=left;
	    //如果右子树的最大长度是大于0的，目前结点大小加上右子树最大长度
	    if(right>0) tmp+=right;
	    //比较目前结点的子树的最大长度
	    maxsum=max(maxsum,tmp);
	    //返回从目前根开始的最大长度
	    return max(0,max(left,right)+root->val);
    }
    int maxPathSum(TreeNode *root) {
	    if(root==NULL)	return 0;
	    int maxsum=INT_MIN;
	    dfs(root,maxsum);
	    return maxsum;
    }
};

题目2：475 · 二叉树的最大路径和 II - LintCode

class Solution {
public :
	int maxPathSum2(TreeNode * root) {
        if (root == NULL)
            return INT_MIN;
        return max(0, max(maxPathSum2(root->left), maxPathSum2(root->right))) + root->val;
    }
};

二叉搜索树

定义：

• 左子树都比根节点小
• 右子树都不小于根节点
  从效果出发：
• 中序遍历是不下降序列
  性质：
• 如果一棵二叉树的中序遍历是不下降序列，则一定不是搜索二叉树
• 如果一棵二叉树的中序遍历是不下降的，不一定是搜索二叉树

题目一：95 · 验证二叉查找树 - LintCode

root 节点，无左右子树的情况下，可以把它的左边下限想象成负无穷，右边上限想象成正无穷。因为root结点要大于left，小于right;

对于左子树的情况就会发现，左节点的下限还是负无穷，而上限已经变成了root 右边也是一样，上限还是正无穷而下限成了root

这里用nullptr 代替了 负无穷和正无穷，比较的时候直接跳过这种情况了，就不用进行比较。

这里采用的思想是从上向下的思考方式。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root==NULL) return true;
        return dfs(root,nullptr,nullptr);
    }
    bool dfs(TreeNode* root, TreeNode* low, TreeNode* high) {
        if (root == NULL) return true;
        if ((low && root->val <= low->val) || (high && root->val >= high->val)) return false;
        return dfs(root->left,low, root) && dfs(root->right, root, high);
    }
};