欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode:二叉树的中序遍历

程序员文章站 2022-05-19 20:58:05
...

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; //访问完,就该访问右边的了。
    }
    
}