BinaryTreeInorderTraversal [source code]
public class BinaryTreeInorderTraversal {
static
/******************************************************************************/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
res.add(cur.val);
cur = cur.right; //cur visited, move ON to right
} else {
TreeNode pre = cur.left; //start point is left rather than cur
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) { //modify
pre.right = cur;
cur = cur.left; //tricky point
} else { //restore
pre.right = null;
res.add(cur.val);
cur = cur.right; //again, visit and move ON to right
}
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
BinaryTreeInorderTraversal.Solution tester = new BinaryTreeInorderTraversal.Solution();
}
}
果然还是有这个问题的, 还是不记得具体怎么写, 完全没有思路, 先bear复习一波;
反正首先普通的Stack做法肯定是可以做一个InOrder, 然后Morris traversal其实也是做到InOrder的; 注意Morris traversal本身是一个需要modify input的做法, 那么这样一个代价的背后, 带来的好处是什么呢? 就是O(1)的space; //不过后面研究了一会儿之后好像发现这个算法的时间可能不如普通的Stack做法, 因为每一个node可能被重复的visit;
正好趁着这个机会复习一波;
这个是G4G上面的一个模板算法:
// Java program to print inorder traversal without recursion and stack
// A binary tree tNode has data, pointer to left child and a pointer to right child
class tNode {
int data;
tNode left, right;
tNode(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
tNode root;
// Function to traverse binary tree without recursion and without stack
void MorrisTraversal(tNode root) {
tNode cur, pre;
if (root == null)
return;
cur = root;
while (cur != null) {
if (cur.left == null) {
System.out.print(cur.data + " ");
cur = cur.right;
} else {
// Find the inorder predecessor of cur
pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
// analyze terminating condition: either pre.right == null or pre.right == cur
// Make cur as right child of its inorder predecessor
if (pre.right == null) {
pre.right = cur;
cur = cur.left; //这一句不好记忆;
} else {
// Revert the changes made in if part to restore the original tree i.e.,fix the right child of predecssor
pre.right = null;
System.out.print(cur.data + " ");
cur = cur.right;
}
}
}
}
public static void main(String args[]) {
// Constructed binary tree is
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(2);
tree.root.right = new tNode(3);
tree.root.left.left = new tNode(4);
tree.root.left.right = new tNode(5);
tree.MorrisTraversal(tree.root);
}
}
再次看这个算法还是感觉很难选, 本身的逻辑其实不是不能理解, 主要是这个代码追求精简, 所以要求visit和restore的两个过程写在一个循环里面, 这个就让整个代码理解, 尤其是自己实现的时候显得很复杂了;
reminder: 在TreeNode或者ListNode类的问题当中, 画图的时候始终记得, 一个node可能有多个child(比如是tree的问题的时候), 但是一个node只可能有一个parent;
注意第二个branch里面的while循环的header是关键: pre.right != null && pre.right != cur. 由此造成这个循环有两种termination condition. 通过对这个termination condition的判断, 我们就可以知道下一步应该是继续向左走, 还是可以直接就restore了;
另外注意这个是一个标准的node traversal操作的循环; header肯定还是一个判断termination用的yes-condition; 有一个需要稍微注意一下的小区别在于, 这个header判断的是探路, 也就是是one level above null. 以前也说过了, 这种header往往能让循环本身的思路简化很多;
另外我认为这个小循环的特征也是为什么Morris只能做到InOrder, 因为我们这里依赖的这个小循环找到的是InOrder predecessor;
可以参考bear上面那张图片: 向右走的过程其实在大while循环的两个branch里面都有可能发生, 而向右走的时候肯定会发生一个visit current的动作; 所以其实两个branch里面都有可能有visit的动作; 不同之处在于第二branch里面的这个visit是伴随着一个restore的动作的 ;
2018-05-02 20:01:42 其实是有点放屁的, 这个算法背代码是没有前途的, 关键还是记忆一个trace; 就拿我最熟悉度BST来模拟就行了;
我还是那个观点, trace这种画图, 不需要保留所有的iteration的记号. 过时的记号直接涂掉就行了;
实现的是没有问题的, 这种算法实现一次也是有好处的, 不过这个算法针对这个问题并不对: 审题啊! 这个题目并不是一个BST, 而是就是一个普通的binary tree; 所以这个算法并不适用! Morris只限定于BST; 就是题目里面的这个[1,null,2,3]的tree其实就是一个例子, 直接就break掉这个代码了;
以上基本是放屁, 这个算法是可以做出来的, Morris的算法代码本身没有任何涉及到key comparison的操作, 还要说仅局限于BST就有点不讲道理; 其实就是typo; 改好之后就AC了; 最后的速度是1ms (30%), 其实是iterative的最优解了, 更快的0ms的基本都是recursion的;
这个是discussion最优解:
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
跟我自己想出来的最优解法(in IterativeDFS)居然不谋而合. 所以实际上这个思路真的是完全没有问题了;
这个是另外一个跟geeks4geeks上面的写法一样的写法:
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
pushAllLeft(root, stack);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
pushAllLeft(cur.right, stack);
}
return res;
}
public void pushAllLeft(TreeNode node, Stack stack){
while (node != null) {
stack.add(node);
node = node.left;
}
}
评论里居然有人提到, 实际上Morris不仅可以实现InOrder, 而且PreOrder和PostOrder也可以实现, 这个是文章: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
在ItrativeDFS里面进行具体的总结;
这个是discussion上面一个年代非常久远的最优解, 不过可以看一下:
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vector;
if(!root)
return vector;
stack<TreeNode *> stack;
stack.push(root);
while(!stack.empty())
{
TreeNode *pNode = stack.top();
if(pNode->left)
{
stack.push(pNode->left);
pNode->left = NULL;
}
else
{
vector.push_back(pNode->val);
stack.pop();
if(pNode->right)
stack.push(pNode->right);
}
}
return vector;
}
};
这个做法有两个特点:
- 非常类似我们stack postorder的ver1, 注意他这里push的操作, push left和push right之间是一个else if的关系, 而不是单纯的consecutive conditional; 这样的做法是可以达到一个类似push beam的操作的;
- 这个做法是destructive的; 事实上, 他最后处理的时候, 就是一个vertical一个vertical的处理的;
- 我发现, 这些iterative DFS的算法好些个都是这种思路, 把一个tree割裂成类似list这样的比较好处理的结构: view tree as collection of lists; 这里这个算法是这样做, Morris PostOrder的算法也是这样做的;
上面这个做法的destructive稍微改动一下就行了: 之所以要break left edge, 其实就是为了防止反复push left, 所以另外一个更好的做法就是维护一个类似flag的记录就行了, 具体的做法是用Map:
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vector;
if(!root)
return vector;
unordered_map<TreeNode *, bool> map;//left child has been visited:true.
stack<TreeNode *> stack;
stack.push(root);
while(!stack.empty())
{
TreeNode *pNode = stack.top();
if(pNode->left && !map[pNode])
{
stack.push(pNode->left);
map[pNode] = true;
}
else
{
vector.push_back(pNode->val);
stack.pop();
if(pNode->right)
stack.push(pNode->right);
}
}
return vector;
}
};
这个的缺点就是需要额外的空间(besides the stack);
最后给出的是一个非常类似我自己写法的做法:
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vector;
stack<TreeNode *> stack;
TreeNode *pCurrent = root;
while(!stack.empty() || pCurrent)
{
if(pCurrent)
{
stack.push(pCurrent);
pCurrent = pCurrent->left;
}
else
{
TreeNode *pNode = stack.top();
vector.push_back(pNode->val);
stack.pop();
pCurrent = pNode->right;
}
}
return vector;
}
};
这个看起来好像有点不一样, 不过你看header基本上就可以理解了; 他这里有两个区别:
- 首先没有explicit的push beam的操作, 而是用类似Stack PostOrder ver1的方法, 用push left else push right的思路来完成一个push beam的操作;
- 其次, 注意
pCurrent = pCurrent->left;这一行, 这个也是类似一个在讨论Stack PreOrder的时候的一个stack-oriented approach to traversal-oriented approach的技巧, 与其push left, 不如go to left. 但是实际上的含义是一样的: 你下一个iteration(node, or subproblem)反正还是继续向左走;
除开这些, 基本上就没有其他的做法了;
Problem Description
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Difficulty:Medium
Total Accepted:210.6K
Total Submissions:452.8K
Contributor: LeetCode
Companies
microsoft
Related Topics
tree hash table stack
Similar Questions
Validate Binary Search Tree Binary Tree Preorder Traversal Binary Tree Postorder Traversal Binary Search Tree Iterator Kth Smallest Element in a BST Closest Binary Search Tree Value II Inorder Successor in BST