题目
-
概述:给定一个二叉树,返回它的前序遍历
要求:使用非递归算法
-
输入:二叉树的根节点
-
输出:前序遍历值列表
-
出处:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
思路
- 前序遍历的顺序是根->左子树->右子树
- 由于访问完左子树后要访问右子树,所以要先把右子树的信息暂存,所以考虑用栈实现
- 根节点入栈
- 重复将栈顶元素出栈直至栈为空
- 栈顶元素有右孩子,将右孩子入栈
- 栈顶元素有左孩子,将左孩子入栈
代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) {
return result;
}
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode top;
stack.push(root);
while (!stack.isEmpty()) {
top = stack.pop();
result.add(top.val);
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
return result;
}
}
网友评论