94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
本题要实现二叉树的中序遍历。这个题应该是很基本的二叉树的遍历题,本科学数据结构对这个是基本要求。不过本科学的是中文教材,只知道前序、中序、后序,不知道对应的英文是什么,WIKI上的Tree traversal图解还是很通俗易懂的:前序(Pre-order),中序(In-order),后序(Post-order)和层次遍历(Level-order)。
前序、中序和后序的区别很容易记,只要记住他们的前、中、后分别是访问根节点的顺序。比如前序顺序是先访问根节点,然后依次访问左右孩子节点。前序:根左右;中序:左根右;后序:左右根。
本题要实现二叉树的中序遍历,如上所述,先访问左子树,然后访问根节点,最后访问右子树。用递归的方法非常简洁直观。递归的完整代码如下:
class Solution {
public:
void work(vector<int>& ans, TreeNode* root)
{
if (root == NULL)
return;
work(ans, root->left); // 左
ans.push_back(root->val); // 根
work(ans, root->right); // 右
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ans;
work(ans, root);
return ans;
}
};
本代码提交AC,用时0MS。
但是Note问能不能用迭代实现以下呢?当然可以,所以可以用递归实现的算法肯定都可以用迭代的方法实现,只是有时候迭代写起来更麻烦。
我的思路是肯定要首先找到树的最左下角的叶子节点,这个节点是最先被访问的,然后访问根节点,最后访问右子树。访问右子树的时候,又是重复之前的操作,首先找到右子树中的最左下角的叶子节点,访问它,然后访问根节点,最后又访问其右子树。
上述过程需要在访问完左孩子之后再访问根节点,但是树中节点的指向是单向的,只能由根访问到孩子,不能由孩子回溯到根。我们不可能在找孩子的同时保存该孩子的父亲节点,这样太麻烦了。于是我想到了用堆栈,在找最左下角的叶子节点的时候,顺便把经过的祖先节点压到堆栈中,当访问完孩子节点后,弹栈,此时的栈顶节点就是父亲节点了。如果父节点有右子树,则进入右子树,重复之前的过程(找右子树的最左下角叶子)。
迭代法的完整代码如下:
class Solution {
public:
void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
{
while (root != NULL) {
tree.push(root);
root = root->left;
}
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<TreeNode*> tree;
putAllLeft(root, tree); // 找最左边的叶子节点
TreeNode* top;
while (!tree.empty()) {
top = tree.top();
ans.push_back(top->val); // 访问左(根)节点
tree.pop();
putAllLeft(top->right, tree); // 访问右节点
}
return ans;
}
};
本代码提交AC,用时0MS。
调试的时候可以使用我之前写过的由数组生成二叉树的函数,挺方便的。
Pingback: LeetCode Binary Tree Preorder Traversal | bitJoy > code
Pingback: LeetCode Binary Tree Postorder Traversal | bitJoy > code