给定一个二叉树, 返回它的 前序遍历.
示例:
输入: [1,null,2,3]
- 1
- \
- 2
- /
- 3
输出: [1,2,3]
进阶: 递归算法很简单, 你可以通过迭代算法完成吗?
思路: 方法一: 采用二叉搜索树的前序遍历, 先判断节点是否为空, 为空则返回 list, 不为空, 则将节点的 val 存入 list, 继续遍历节点的左子节点和右子节点, 依次进行得到最终结果.
方法二: 采用借助栈数据结构的非遍历方法.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public List<Integer> preorderTraversal(TreeNode root) {
- ArrayList<Integer> list = new ArrayList<Integer>();
- // 方法一: 采用递归遍历, 测试用例执行速度快
- //if(root==null)
- // return list;
- //return preorder(root,list);
- // 方法二: 借用栈数据结构的非递归遍历, 测试用例执行速度慢
- Stack<TreeNode> stack = new Stack();
- if(root==null) return list;
- stack.push(root);
- while(!stack.isEmpty()){
- root = stack.pop();
- if(root!=null)
- list.add(root.val);
- if(root.right!=null)
- stack.push(root.right);
- if(root.left!=null)
- stack.push(root.left);
- }
- return list;
- }
- private ArrayList<Integer> preorder(TreeNode node,ArrayList<Integer> list){
- if(node==null)
- return list;
- list.add(node.val);
- list = preorder(node.left,list);
- list = preorder(node.right,list);
- return list;
- }
- }
来源: https://www.cnblogs.com/wenbinshen/p/10601800.html