Leetcode: 二叉树的中序遍历
中序遍历的流程:一直往左找,找到最左边的元素访问了之后,因为不存在左孩纸,所以访问完之后,再访问右子树,当右子树访问完,说明该左节点访问结束,就该回溯到上一个左节点,以此类推。
题目:
给定一个二叉树,返回它的中序遍历。
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
Python 实现
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
"""
思路:先往左访问到底,然后访问最左的第一个元素(不存在左孩子了),再去访问他的右子树,右子树访问完,回溯到上一个左孩子,进行访问,
"""
result = []
stack = []
while True:
while root:
stack.append(root)
root = root.left # 一直往左走
if len(stack) == 0:
return result
root = stack.pop()
result.append(root.val) # 访问最左边的
root = root.right # 访问最右边的
C语言实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int *result = (int *)malloc(sizeof(int)*100);
struct TreeNode *stack[100];
int top = -1;
int i = 0;
while(true){
while(root){
stack[++top] = root;
root = root->left; //往左走到底,就可以访问
}
if(top == -1){
*returnSize = i;
return result;
}
root = stack[top--]; //拿到最左边的点,访问
result[i++] = root->val;
root = root->right; //访问完,就该访问右边的了。
}
}