每日算法 二叉树的前序遍历

例题：144. 二叉树的前序遍历

题目描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

代码：

//动态规划版
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }
}
//输入一个节点，返回以该节点为根的二叉树的前序遍历结果

//回溯版
class Solution {
    LinkedList<Integer> result = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
        traverse(root);
        return result;
    }
    // 二叉树遍历函数
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序遍历位置
        result.add(root.val);
        traverse(root.left);
        traverse(root.right);
    }
}

动态规划思路和回溯思路之间的差别就在于递归的地方。动态规划算法是使用了 Java 中本身的 add() 和 addAll() 两个 LinkedList 类的方法，并且是从根节点开始存储，让根节点的左子结点和右子节点进行自身函数的递归得到集合一起用 addAll() 方法加入进 LinkedList 类的 result 中；而回溯算法中是通过一次次将节点遍历，在遍历函数中将节点一个个加入 LinkedList 类的 result 中。

虽然本质上两个都是通过遍历的方法将前序遍历的二叉树保存下来，但细节上还是有一定的差距。