二叉树后序遍历的非递归实现

给定一棵二叉树,不使用递归,迭代地后序遍历并输出树中的元素

 二叉树的后序遍历很容易采用递归方式实现:

void postOrderTraversal(BinaryTree *p) {
  if (!p) return;
  postOrderTraversal(p->left);
  postOrderTraversal(p->right);
  cout << p->data;
}

后序遍历是二叉树三种遍历的非递归算法中最难实现的一种,在做这道题目之前可以首先尝试一下这一题,因为它相对简单一些:Binary Search Tree In-Order Traversal Iterative Solution

三种遍历的非递归实现中最容易的是先序遍历。

后序遍历是一种非常有用的树操作,例如它可以被用于下面的场景:

树的删除。为了释放树结构的内存,某节点在被释放以前,其左右子树的节点首先应当被释放掉。
后缀表示法(逆波兰表示法)

如果在遍历树时维护一个visited标记,问题可以比较直观地解决。在此不详细讨论该方法 ...

继续阅读

[LeetCode]Binary Tree Inorder Traversal

题目描述:

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

题目大意:

非递归实现二叉树的中序遍历 ...

继续阅读

[LeetCode]Duplicate Emails

题目描述:

Write a SQL query to find all duplicate emails in a table named Person.

+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+
For example, your query should return the following for the above ...

继续阅读

[LeetCode]Employees Earning More Than Their Managers

题目描述:

The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.

+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000 ...

继续阅读

年度归档