版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
题目
- Binary Tree Inorder Traversal（二叉树中序遍历）
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
return[1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".
递归思想
思路
中序遍历的递归思想实现。顺序为：左 → 根 → 右。
代码
vector<int> inorderTraversal(TreeNode *root)
{
// 二叉树中序遍历
vector<int > v;
if(root == NULL)return v;
inorder_help(root, v);
return v;
}
/*
* 中序遍历顺序：左 → 根 → 右。
*/
void inorder_help(TreeNode *root, vector<int > &v)
{
if(!root)return;
inorder_help(root->left, v);// 递归左子树
v.push_back(root->val);// 保存根
inorder_help(root->right, v);// 递归右子树
}
非递归思想
思路
用非递归模拟二叉树的中序遍历，思路是：优先遍历根节点的左孩子结点，放入一个栈中，遍历到底；然后从栈中取结点，栈的特点是后进先出，从最后的节点开始加入vector数组；接着遍历该结点的右孩子结点，把该孩子结点当作根节点遍历左孩子结点。
实现的思想和递归是一样的，就是根据中序遍历的特点，中序遍历顺序：左 → 根 → 右，即：
inorder(root -> left);// 左子树
get(root -> val);// 根
inorder(root -> right);// 右子树
代码
vector<int> inorderTraversal(TreeNode *root)
{
vector<int > v;
stack<TreeNode* > s;
TreeNode *node = root;
while(!s.empty() || node!=NULL)
{
// 以当前结点为根，顺着左子树找到底
while(node != NULL)
{
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
v.push_back(node->val); // 左边遍历完了，保存根结点
node = node->right; // 遍历右子树结点
}
return v;
}
以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
