Binary Tree Depth Order Traversal

前面我们解决了tree的level order遍历问题，这里我们需要来处理tree的depth order，也就是前序，中序和后序遍历。

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values. For example:
Given binary tree {1,#,2,3}, 1. 1 2. \ 3. 2 4. / 5. 3

return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? 给定一颗二叉树，使用迭代的方式进行前序遍历。 因为不能递归，所以我们只能使用stack来保存迭代状态。 对于前序遍历，根节点是最先访问的，然后是左子树，最后才是右子树。当访问到根节点的时候，我们需要将右子树压栈，这样访问左子树之后，才能正确地找到对应的右子树。 代码如下： 1. class Solution { 2. public: 3. vector preorderTraversal(TreeNode root) { 4. vector vals; 5. if(root == NULL) { 6. return vals; 7. } 8. 9. vector nodes; 10. 11. //首先将root压栈 12. nodes.push_back(root); 13. 14. while(!nodes.empty()) { 15. TreeNode n = nodes.back(); 16. vals.push_back(n->val); 17. 18. //访问了该节点，出栈 19. nodes.pop_back(); 20. 21. //如果有右子树，压栈保存 22. if(n->right) { 23. nodes.push_back(n->right); 24. } 25. 26. //如果有左子树，压栈保存 27. if(n->left) { 28. nodes.push_back(n->left); 29. } 30. } 31. 32. return vals; 33. } 34. };

Binary Tree Inorder Traversal

给定一颗二叉树，使用迭代的方式进行中序遍历。 对于中序遍历，首先遍历左子树，然后是根节点，最后才是右子树，所以我们需要用stack记录每次遍历的根节点，当左子树遍历完成之后，从stack弹出根节点，得到其右子树，开始新的遍历。 代码如下： 1. class Solution { 2. public: 3. vector inorderTraversal(TreeNode root) { 4. vector vals; 5. if(root == NULL) { 6. return vals; 7. } 8. 9. vector nodes; 10. TreeNode p = root; 11. while(p || !nodes.empty()) { 12. //这里一直遍历左子树，将根节点压栈 13. while(p) { 14. nodes.push_back(p); 15. p = p->left; 16. } 17. 18. if(!nodes.empty()) { 19. p = nodes.back(); 20. vals.push_back(p->val); 21. 22. //将根节点弹出，获取右子树 23. nodes.pop_back(); 24. p = p->right; 25. } 26. } 27. 28. return vals; 29. } 30. };

Binary Tree Postorder Traversal

给定一颗二叉树，使用迭代的方式进行后序遍历。 对于后序遍历，首先遍历左子树，然后是右子树，最后才是根节点。当遍历到一个节点的时候，首先我们将右子树压栈，然后将左子树压栈。这里需要注意一下出栈的规则，对于叶子节点来说，直接可以出栈，但是对于根节点来说，我们需要一个变量记录上一次出栈的节点，如果上一次出栈的节点是该根节点的左子树或者右子树，那么该根节点可以出栈，否则这个根节点是新访问的节点，将右和左子树分别压栈。 代码如下： 1. class Solution { 2. public: 3. vector postorderTraversal(TreeNode root) { 4. vector vals; 5. if(root == NULL) { 6. return vals; 7. } 8. 9. vector nodes; 10. TreeNode pre = NULL; 11. 12. nodes.push_back(root); 13. 14. while(!nodes.empty()) { 15. TreeNode* p = nodes.back(); 16. //如果不判断pre，我们就没法正确地出栈了 17. if((p->left == NULL && p->right == NULL) || 18. (pre != NULL && (pre == p->left || pre == p->right))) { 19. vals.push_back(p->val); 20. nodes.pop_back(); 21. pre = p; 22. } else { 23. //右子树压栈 24. if(p->right != NULL) { 25. nodes.push_back(p->right); 26. } 27. 28. //左子树压栈 29. if(p->left != NULL) { 30. nodes.push_back(p->left); 31. } 32. } 33. } 34. 35. return vals; 36. } 37. };

总结

可以看到，树的遍历通过递归或者堆栈的方式都是比较容易的，网上还有更牛的不用栈的方法，只是我没理解，就不做过多说明了。