丽水做企业网站的地方,广告费计入什么科目,开发聊天软件成本,[ 1500元做网站_验收满意再付款! ]_沛县网络公司题意理解#xff1a; 首先明确二叉树的定义#xff0c;对于所有节点#xff0c;根节点的值大于左子树所有节点的值#xff0c;小于右子树所有节点的值。 注意一个误区#xff1a; 根节点简单和左孩子#xff0c;右孩子比大小是不够的#xff0c;要和子树比#xff0c;… 题意理解 首先明确二叉树的定义对于所有节点根节点的值大于左子树所有节点的值小于右子树所有节点的值。 注意一个误区 根节点简单和左孩子右孩子比大小是不够的要和子树比如下图 他每个节点根节点大于左孩子小于右孩子。 但是他的每个根节点不大于左子树的所有节点的值小于右子树所有节点的值它是无序的不是一颗二叉搜索树. 二叉搜索树的特点 二叉搜索树的中序遍历是单调递增的数列。 1.数列递增判断【其实也是递归】
已知二叉搜索树的中序遍历的单调递增的所以只要判断二叉树中序遍历数列是否单调递增即可。
//一个合法的搜索二叉树的中序遍历应该是严格的递增数列ListInteger reusltnew ArrayList();public boolean isValidBST(TreeNode root) {if(rootnull) return true;//中序遍历是递增序列//左节点处理boolean leftisValidBST(root.left);//根节点处理//数列为空的时候直接往进加//数列不为空的时候与数列最后一位的值比大小// 比它大则说明单调递增// 比它小则说明不符合单调递增返回falseif(reuslt.size()0||reuslt.get(reuslt.size()-1) root.val){reuslt.add(root.val);}else{return false;}//右节点处理boolean rightisValidBST(root.right);return leftright;}
2.递归
//递归//为什么用long?//因为节点值-2^31 Node.val 2^31 - 1,囊括了int范围所有值//maxValue初始为比int最小值还小的值//故取long的最小值long的取值范围比int更广Long maxValueLong.MIN_VALUE;public boolean isValidBST2(TreeNode root) {if(rootnull) return true;//中序遍历//左子树验证boolean leftisValidBST2(root.left);//中节点处理// maxValue总是保存当前递增的最大值// 当前值比maxValue大则说明符合单调递增将当前值给maxValue// 当前值比maxValue小则说明不符合单调递增返回falseif(maxValueroot.val) maxValue(long)root.val;else return false;//右子树验证boolean rightisValidBST2(root.right);return leftright;}
3.递归双指针优化
把maxValue改为使用 TreeNode pre,来指向遍历的前一个节点root总是指向当前节点不需要复杂的考虑long还是int的问题其余地方其实是一样的。
//递归双指针TreeNode prenull;public boolean isValidBST3(TreeNode root) {if(rootnull) return true;boolean leftisValidBST3(root.left);if(prenull||pre.val root.val) preroot;else return false;boolean rightisValidBST3(root.right);return leftright;}
4.迭代
迭代还是之前遍历的套路需要使用栈保存节点模拟递归会有一点麻烦。
public boolean isValidBST4(TreeNode root) {if(rootnull) return true;//模拟递归的栈StackTreeNode stacknew Stack();stack.push(root);TreeNode prenull;while(!stack.isEmpty()){TreeNode tmpRootstack.peek();//当前节点是否为空if(tmpRoot!null){//若节点不为空则弹出当前节点//由于栈总是先进后出故左中右节点的入栈顺序应为右中左//为了识别中节点在中间节点入栈后加入一个null值所有null值后总是中间节点用于判断。//左右节点不为空时入栈所以左右节点不会引入null值stack.pop();if(tmpRoot.right!null)stack.push(tmpRoot.right);stack.push(tmpRoot);stack.push(null);if(tmpRoot.left!null)stack.push(tmpRoot.left);}else{//若当前节点为空则只有可能我们是在之前的操作中引入的null值//将当前null值弹出后取下一位进行比较//若遍历前一位节点为空或当前节点大于pre节点值则将当前节点给pre//否则当前节点小于pre的值不符合单调增返回falsestack.pop();TreeNode tmpstack.pop();if(prenull||tmp.valpre.val) pretmp;else return false;}}return true;}
5.分析 时间复杂度 数列递增O(n) 递归:O(n) 递归双指针O(n) 迭代: O(n) 空间复杂度 数列递增O(n) 递归:O(1) 递归双指针O(1) 迭代O(n)
