Recover Binary Search Tree:以前的解法通不过了 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - Recover Binary Search Tree:以前的解法通不过了

相关主题
● help: leetcode "Recover Binary Search Tree" -- 附代码	● 150上这个是不是不对？ (转载)
● 问一个题目	● 面试的时候 binary tree的delete也要15分钟之内写完么？
● 发现一个很恶心的基础问题	● 问个二叉树删除结点的问题
● MS onsite面经	● 一道题：2个BST，按大小顺序打印两棵树的所有节点
● leetcode的ＯＪ也会有错吗？？	● leetcode里面的Recover Binary Search Tree怎么用O(1)space
● 请教大家一个问题：Maximum Height (Depth) of a Binary Tree Using PreOrder Traversal	● 有没有人同觉得Recover Binary Search Tree的solution using O(n) space并不是那么straight forward么？
● [leetcode] Maximum Depth of Binary Tree	● 自己写了个graph的class但是不work 求指点
● A onsite被拒,面经,求分析失败原因	● 请问LOWEST COMMON ANCESTOR OF A BINARY TREE， treenode 只有parent，没有left，right

相关话题的讨论汇总
话题: treenode话题: null话题: root话题: prev

进入JobHunting版参与讨论

(共1页)

l**********9
发帖数: 537

这个流行的解法通不过｛0，1｝的test case，上个星期还可以通过。看不出什么问题
，你们的还能通过吗？
public class Solution {
TreeNode node1 = null;
TreeNode node2 = null;
TreeNode prev = null;
public void recoverTree(TreeNode root) {
inorderTraverse(root);
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}

private void inorderTraverse(TreeNode root) {
if (root == null)
return;
inorderTraverse(root.left);
if (prev != null) {
if (root.val <= prev.val) {
if (node1 == null)
node1 = prev;
node2 = root;
}
}
prev = root;
inorderTraverse(root.right);
}
}

(共1页)

进入JobHunting版参与讨论

相关主题
● 请问LOWEST COMMON ANCESTOR OF A BINARY TREE， treenode 只有parent，没有left，right	● leetcode的ＯＪ也会有错吗？？
● 再问个C++的基础问题(in order traversal)	● 请教大家一个问题：Maximum Height (Depth) of a Binary Tree Using PreOrder Traversal
● 大牛帮我看看这哪错了? iterative inorder traversal	● [leetcode] Maximum Depth of Binary Tree
● inorder traversal的空间复杂度是O(N) 还是O(logN)?	● A onsite被拒,面经,求分析失败原因
● help: leetcode "Recover Binary Search Tree" -- 附代码	● 150上这个是不是不对？ (转载)
● 问一个题目	● 面试的时候 binary tree的delete也要15分钟之内写完么？
● 发现一个很恶心的基础问题	● 问个二叉树删除结点的问题
● MS onsite面经	● 一道题：2个BST，按大小顺序打印两棵树的所有节点

相关话题的讨论汇总
话题: treenode话题: null话题: root话题: prev

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天