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

问题描述

http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/

    1
   / \
  2   3
 / \
4   5

解题思路

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

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

参考代码1

遍历。

构造一个遍历helper函数：

1. 根节点为空，则返回
2. 把根节点值放入result
3. 用helper函数遍历左子树
4. 用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分治法，先分别对左右子树下手，拿到左右子树结果后，最后回到根节点统一处理。

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

时间复杂度：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; 
    } 
}

相关题目

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