LintCode 66. Binary Tree Preorder Traversal 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/
Given a binary tree, return the preorder traversal of its nodes’ values.
Example
Given:
1
/ \
2 3
/ \
4 5
return [1,2,4,5,3]
.
解题思路
题目是问如何对Binary Tree二叉树进行前序遍历。
两种方法解决:遍历、分治。
参考代码1
遍历。
构造一个遍历helper函数:
- 根节点为空,则返回
- 把根节点值放入result
- 用helper函数遍历左子树
- 用helper函数遍历右子树
时间复杂度:O(N)
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); traverse(root, result); return result; } private void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } result.add(root.val); traverse(root.left, result); traverse(root.right, result); } }
参考代码2
Divide and Conquer分治法,先分别对左右子树下手,拿到左右子树结果后,最后回到根节点统一处理。
- root为空,则返回
- 分开得到左右子树的前序遍历的各自结果。
- 最后将根节点值和左右子树结果合并。
时间复杂度:O(N)
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); if (root == null) { return result; } ArrayList<Integer> left = preorderTraversal(root.left); ArrayList<Integer> right = preorderTraversal(root.right); result.add(root.val); result.addAll(left); result.addAll(right); return result; } }