Binary Tree Preorder Traversal
题目地址
https://leetcode.com/problems/binary-tree-preorder-traversal/description/
题目描述
1 | Given a binary tree, return the preorder traversal of its nodes' values. |
思路
这道题目是前序遍历,这个和之前的leetcode 94 号问题 - 中序遍历
完全不一回事。
前序遍历是根左右
的顺序,注意是根
开始,那么就很简单。直接先将根节点入栈,然后 看有没有右节点,有则入栈,再看有没有左节点,有则入栈。 然后出栈一个元素,重复即可。
其他树的非递归遍历课没这么简单
关键点解析
二叉树的基本操作(遍历) > 不同的遍历算法差异还是蛮大的
如果非递归的话利用栈来简化操作
如果数据规模不大的话,建议使用递归
递归的问题需要注意两点,一个是终止条件,一个如何缩小规模
终止条件,自然是当前这个元素是null(链表也是一样)
由于二叉树本身就是一个递归结构, 每次处理一个子树其实就是缩小了规模, 难点在于如何合并结果,这里的合并结果其实就是
mid.concat(left).concat(right)
, mid是一个具体的节点,left和right递归求出即可
代码
1 | /* |
Binary Tree Preorder Traversal