[数据结构与算法]LeetCode-144. 二叉树的前序遍历

1.题目地址

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

2.题目理解

? ? ? ? 对于一个二叉树，前序遍历就是先打印父节点，然后依次打印左子节点和右子节点。

3.我的思路

? ? ? ? 3.1:递归

????????首先想到的是递归，先访问父节点，然后依次访问左子节点和右子节点。递归的终止条件就是当前节点为空节点。

代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        frontSearch(result, root);
        return result;
    }

    private void frontSearch(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        frontSearch(result, root.left);
        frontSearch(result, root.right);
    }
}

? ? ? ? 3.2迭代

? ? ? ? 可以使用栈，每当访问一个节点时，先取出节点的值放入结果列表中，如果右节点不为空，则将右节点入栈，如果左节点也不为空，则将左节点也入栈。然后当栈不为空时，依次弹出栈顶的节点，循环上述操作。因为后进先出，可以保证父节点->左节点->右节点的顺序访问。

代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> treeNodes = new Stack<>();
        if (root != null) {
            treeNodes.add(root);
        }

        TreeNode curNode;
        while (!treeNodes.isEmpty()) {
            curNode = treeNodes.pop();
            result.add(curNode.val);
            if (curNode.right != null) {
                treeNodes.add(curNode.right);
            }
            if (curNode.left != null) {
                treeNodes.add(curNode.left);
            }
        }
        return result;
    }

}