以下是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。