validate binary tree
昨天簡書非常不穩(wěn)定，不知道是我自己網(wǎng)絡(luò)的原因，還是簡書的服務(wù)器不穩(wěn)定戏锹。所以昨天寫的今天才發(fā)火诸。
今天是一道題目锦针，來自LeetCode，難度為Medium置蜀，Acceptance為20.3%奈搜。
題目如下
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先，老規(guī)矩看到二叉樹首先想到三種遍歷方式盯荤。針對該題目馋吗，首先想到采用后序遍歷的方法最好，即先判斷左右子樹是不是valid秋秤，然后判斷根是不是valid宏粤。
這樣做當(dāng)然可以，但是時間復(fù)雜度卻比較高灼卢。仔細想想其實這里不是必須使用后序遍歷绍哎。
所以這里可以這樣做，對于一個任意一個節(jié)點鞋真，若它是左子樹崇堰，那么它應(yīng)該比它的父節(jié)點小；若它是右子樹灿巧，那么它應(yīng)該比它的父節(jié)點大赶袄。
對于根節(jié)點揽涮，因為它沒有父節(jié)點，直接傳遞最大最小的整數(shù)值饿肺。
最后我們來看代碼蒋困。
代碼如下
Java版
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}
關(guān)注我
該公眾號會每天推送常見面試題，包括解題思路是代碼敬辣，希望對找工作的同學(xué)有所幫助
image
