LintCode 66. Binary Tree Preorder Traversal 原创Java参考解答

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:

return [1,2,4,5,3].

解题思路

题目是问如何对Binary Tree二叉树进行前序遍历。

两种方法解决:遍历、分治。

参考代码1

遍历。

构造一个遍历helper函数:

  1. 根节点为空,则返回
  2. 把根节点值放入result
  3. 用helper函数遍历左子树
  4. 用helper函数遍历右子树

时间复杂度:O(N)

参考代码2

Divide and Conquer分治法,先分别对左右子树下手,拿到左右子树结果后,最后回到根节点统一处理。

  1. root为空,则返回
  2. 分开得到左右子树的前序遍历的各自结果。
  3. 最后将根节点值和左右子树结果合并。

时间复杂度:O(N)

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注