树后序遍历性能

我试图自己去获取迭代后序遍历。我的解决方案得到了有限时间超过了Leetcode Online Judge 树后序遍历性能

public List<Integer> postorderTraversalIterativel(TreeNode root) { 
    List<Integer> ret = new LinkedList<Integer>(); 
    Stack<TreeNode> stack = new Stack<TreeNode>(); 
    TreeNode cur = root; 
    while (cur != null || !stack.isEmpty()) { 
     if (cur != null) { 
      stack.push(cur); 
      cur = cur.left; 
     } else { 
      TreeNode parent = stack.peek(), child = null; 
      if (parent.right == null) { 
       // pop hard 
       stack.pop(); 
       while (parent.right == child && !stack.isEmpty()) { 
        child = parent; 
        ret.add(child.val); 
        parent = stack.pop(); 
       } 
      } else { 
       cur = parent.right; 
      } 
     } 
    } 
    return ret; 
}

而从wikipedia正式实施可能通过测试。

public List<Integer> postorderTraversalIterativel(TreeNode root) { 
    List<Integer> ret = new LinkedList<Integer>(); 
    Stack<TreeNode> stack = new Stack<TreeNode>(); 
    TreeNode cur = root, lastVisited = null; 
    while (cur != null || !stack.isEmpty()) { 
     if (cur != null) { 
      stack.push(cur); 
      cur = cur.left; 
     } else { 
      TreeNode parent = stack.peek(); 
      if (parent.right != null && lastVisited != parent.right) { 
       // make sure pop all the node has right child of the 
       // previous pop 
       cur = parent.right; 
      } else { 
       stack.pop(); 
       ret.add(parent.val); 
       lastVisited = parent; 
      } 
     } 
    } 
    return ret; 
}

通过检查代码，我无法明白为什么我的执行速度比官方慢。任何人都可以指出发生了什么？（有可能我的解决方案在逻辑上是错误的，但是我的解决方案在我进行单元测试的时候失败了，并且单元测试快速完成...）。欢迎任何评论。

public void testPostorderTraversal1() { 
    TreeNode root = new TreeNode(3); 
    TreeNode right = new TreeNode(1); 
    TreeNode rightLeft = new TreeNode(2); 
    root.right = right; 
    right.left = rightLeft; 

    List<Integer> list = new LinkedList<Integer>(); 
    list.add(2); 
    list.add(1); 
    list.add(3); 

    assertEquals(list.toString(), sut.postorderTraversal(root).toString()); 
} 

public void testPostorderTraversal2() { 
    TreeNode root = new TreeNode(1); 
    TreeNode right = new TreeNode(2); 
    root.right = right; 

    List<Integer> list = new LinkedList<Integer>(); 
    list.add(2); 
    list.add(1); 

    assertEquals(list.toString(), sut.postorderTraversal(root).toString()); 
}

来源

2014-06-09 Mingtao Zhang

为什么parent.right == child需要while（parent.right == child &&！stack.isEmpty（））？如果（parent.right == null）的计算结果为true，并且在此之前将child设置为null，则可以到while循环，因此parent.right和child在该阶段始终为null，因此总是计算结果为true我猜。这不会让你的代码超过时间限制，但只是发现它 –

@Kartik_Koro我正在改变while循环内的父母和孩子。 –

你的代码有可能做无限循环。

您'testPostorderTraversal1'unitest未完成。

如果有任何有右子节点的节点有了子节点，就不能完成。

来源

2014-07-14 07:25:22 Mastojun

！认为它通过了测试。将尽快测试 - - 。 –

@MingtaoCraigZhang http://ideone.com/VQGh9Y TLE – Mastojun

似乎正在为这种情况工作... –

树后序遍历性能

回答

相关问题