144.二叉树的前序遍历

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

示例 1：

1
2
输入：root = [1,null,2,3]
输出：[1,2,3]

Solution

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

tips：逆前序遍历：右—->左—->根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reversePreorder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归遍历右子树
        reversePreorder(root.right);
        // 再递归遍历左子树
        reversePreorder(root.left);
        // 最后访问根节点
        System.out.print(root.val + " ");
    }
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}