以下是Python语言编写的程序,实现将一个二叉树中的节点按照中序遍历的顺序输出:

python 
class TreeNode: 
    def __init__(self, val=0, left=None, right=None): 
        self.val = val 
        self.left = left 
        self.right = right 
 
def inorderTraversal(root: TreeNode) -> List[int]: 
    res = [] 
    if not root: 
        return res 
    stack = [] 
    curr = root 
    while curr or stack: 
        while curr: 
            stack.append(curr) 
            curr = curr.left 
        curr = stack.pop() 
        res.append(curr.val) 
        curr = curr.right 
    return res 

其中,TreeNode类表示二叉树的节点,inorderTraversal函数实现了中序遍历,并返回遍历结果。程序使用了栈来实现中序遍历,具体实现过程如下:

1. 初始化一个空列表res,如果根节点为空,则直接返回res;

2. 初始化一个空栈stack和一个指针curr,将curr指向根节点;

3. 当curr不为空或stack不为空时,执行以下操作:

1. 当curr不为空时,将curr入栈,并将curr指向其左子节点,直到curr为空;

2. 当curr为空时,从栈中弹出一个节点,并将其值加入res中;

3. 将curr指向弹出节点的右子节点;

4. 遍历结束后,返回res。


评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!