資訊專欄INFORMATION COLUMN
摘要：小鹿題目驗(yàn)證二叉搜索樹給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。
Time：2019/4/24
Title: Vaildata Binary Search Tree
Difficulty: Medium
Author: 小鹿
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.
給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。
假設(shè)一個(gè)二叉搜索樹具有如下特征：
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
Example 1:
Input:
2
/
1 3
Output: true
Example 2:
5
/
1 4
/
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node"s value
is 5 but its right child"s value is 4.
Solve:
看到此題的入手點(diǎn)就是上方提出的三點(diǎn)二叉搜索樹的三點(diǎn)要求：
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
1）以上三點(diǎn)要求最容易解決的就是一個(gè)中序遍歷，判斷遍歷出的每個(gè)元素后一個(gè)元素是否大于前一個(gè)元素，如果不符合條件，那么就不是一個(gè)二分搜索樹。
1）定義全局的 boolean 變量，用來返回是否為 二叉搜索樹。2）定義一個(gè)邊界值賦予 max 變量。每遍歷一次，如果符合前后大小的要求，就將當(dāng)前節(jié)點(diǎn)的值賦值給 max 變量，用于下一次遍歷的結(jié)點(diǎn)的大小比較。如果不符合要求，我們將其布爾變量置為 false。
3）整個(gè)過程是用遞歸來解決的，在理解上還是有點(diǎn)不符合常規(guī)思路的。也是整個(gè)問題分析中最重要的一點(diǎn)。
var isValidBST = function(root) {
// boolean 變量
let isValidBSTFlag = true;
// 最大值變量
let max = -Number.MAX_VALUE;
const orderSearch = root => {
// 終止條件（判斷當(dāng)前結(jié)點(diǎn)是否為 null）
if (root) {
// 中序遍歷
orderSearch(root.left);
// 判斷遍歷前后的值是否逐漸升序
if (root.val > max) {
// 存儲(chǔ)當(dāng)前結(jié)點(diǎn)值，進(jìn)行下一次比較
max = root.val;
} else {
// 當(dāng)前節(jié)點(diǎn)值小于前一結(jié)點(diǎn)值，返回 false
isValidBSTFlag = false;
}
orderSearch(root.right);
}
}
orderSearch(root);
return isValidBSTFlag;
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/103986.html
摘要：小鹿題目路徑總和給定一個(gè)二叉樹和一個(gè)目標(biāo)和，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。說明葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。 Time：2019/4/26Title: Path SumDifficulty: EasyAuthor: 小鹿 題目：Path Sum（路徑總和） Given a binary tree and a sum, determin...
摘要：小鹿題目二叉樹中序遍歷給定一個(gè)二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點(diǎn)難度，用一般的迭代循環(huán)來實(shí)現(xiàn)。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目：Binary Tree Inorder Traversal（二叉樹中序遍歷...
摘要：算法思路判斷樹是否為空同時(shí)也是終止條件。分別對(duì)左右子樹進(jìn)行遞歸。代碼實(shí)現(xiàn)判斷當(dāng)前樹是否為左右子樹結(jié)點(diǎn)交換分別對(duì)左右子樹進(jìn)行遞歸返回樹的根節(jié)點(diǎn)歡迎一起加入到開源倉庫，可以向提交您其他語言的代碼。 Time：2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿 題目：Invert Binary Tree（反轉(zhuǎn)二叉樹） ...
摘要：小鹿題目二叉樹的最大深度給定一個(gè)二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿 題目：Maximum Depth of Binary Tre...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 2741·2023-04-26 02:02
閱讀 2621·2023-04-25 20:38
閱讀 4162·2021-09-26 09:47
閱讀 3150·2021-09-10 10:50
閱讀 3814·2021-09-07 09:58
閱讀 3359·2019-08-30 15:54
閱讀 2722·2019-08-30 15:54
閱讀 1941·2019-08-29 17:03
