資訊專欄INFORMATION COLUMN
摘要：題目解答想法很簡單，找到兩個(gè)順序不對的點(diǎn)，交換。但是如何知道這兩個(gè)點(diǎn)的順序是不對的呢因?yàn)槭亲笾杏?，所以我們可以用的方法模板代碼如下
題目：
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
解答：
想法很簡單，找到兩個(gè)順序不對的點(diǎn)，交換。但是如何知道這兩個(gè)點(diǎn)的順序是不對的呢？因?yàn)锽ST是左<中<右，所以我們可以用in-order traverse的方法：
In-order traverse模板：
public void inOrderTraverse{
inOrderTraverse(root.left);
//do something
inOrderTraverse(root.right);
}
代碼如下：
public class Solution {
private TreeNode first = null, second = null;
private TreeNode prev = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
Traverse(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void Traverse(TreeNode root) {
if (root == null) return;
Traverse(root.left);
if (first == null && prev.val > root.val) {
first = prev;
}
if (first != null && prev.val > root.val) {
second = root;
}
prev = root;
Traverse(root.right);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64884.html
摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來，最后回原來正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。思想來自于的代碼實(shí)現(xiàn)。 跳過總結(jié)請點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.v...
摘要：題目鏈接參考這篇文章鏈接題目鏈接還是一樣的，用，或者保存和。題目鏈接題目鏈接按照的順序最后再一下。 Inorder Binary Tree Inorder Traversal lc題目鏈接：https://leetcode.com/problems... recursion： public class Solution { public List inorderTraversa...
Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...
摘要：建立兩個(gè)樹結(jié)點(diǎn)，先用找到在的位置，讓作為的根節(jié)點(diǎn)找到的位置后，指向。此時(shí)，用代替與連接就可以了。 Problem Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tr...
摘要：題目要求檢驗(yàn)二叉查找樹是否符合規(guī)則。二叉查找樹是指當(dāng)前節(jié)點(diǎn)左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。 題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...
閱讀 3599·2023-04-26 02:55
閱讀 2866·2021-11-02 14:38
閱讀 4146·2021-10-21 09:39
閱讀 2856·2021-09-27 13:36
閱讀 3967·2021-09-22 15:08
閱讀 2657·2021-09-08 10:42
閱讀 2811·2019-08-29 12:21
閱讀 678·2019-08-29 11:22
