LeetCode_12_BinaryTreePreOrderTraversal

LeetCode

发布日期: 2022-03-21

更新日期: 2022-03-21

文章字数: 700

阅读时长: 3 分

阅读次数:

1. question: 二叉树的前序遍历（简单）

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal

示例 1：

示例1

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

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

示例 4：

示例4

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

示例 5：

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

提示：

1 2	树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100

2. answers

首先需要明确一点，二叉树是一个递归的数据结构，二叉树的左右孩子节点仍然是一棵二叉树。

2.1 递归解法

代码如下所示：

public class Solution_0010 {

    public static void recurive(TreeNode root, List<Integer> result) {

        if(root != null) {

            // 先序，所以先访问根
            result.add(root.val);

            // 再将递归遍历左子树
            recurive(root.left, result);

            // 再递归遍历右子树
            recurive(root.right, result);
        }
    }

    // 递归做法
    public static List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        recurive(root, result);

        return result;
    }
    
    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(2, tn1, null);
        TreeNode root = new TreeNode(1, null, tn2);

        List<Integer> integers = preorderTraversal(root);
//        List<Integer> integers = preorderTraversal(null);
//        List<Integer> integers = preorderTraversal(new TreeNode(1));
        for(Integer i : integers){
            System.out.println(i);
        }
        
    }
}

2.2 迭代解法

除了递归，还可以采用迭代的方式来做。二叉树无论什么顺序遍历，其左右子树都是分开遍历的，因此，我们需要保存根节点或者左右子树的根节点。这样才能在左子树访问完之后，依旧能够获取右子树的根节点。可以采用栈来做，在访问到当前根节点之后，将其右节点和左节点依次放入到栈中，这样在出栈的时候，先访问左节点，再访问右节点。

public class Solution_0010 {

    // 迭代做法（非递归）
    public static List<Integer> preorderTraversalPlus(TreeNode root){

        Stack<TreeNode> sta = new Stack<>();
        List<Integer> result = new ArrayList<>();

        if(root != null) {
            sta.push(root);
        }

        while(!sta.isEmpty()){
            root = sta.pop();
            result.add(root.val);

            // 注意，先序是 中左右，所以入栈的时候，要先放右子树，再放左子树
            if(root.right != null) {
                sta.push(root.right);
            }

            if(root.left != null) {
                sta.push(root.left);
            }
        }

        return result;
    }

    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(2, tn1, null);
        TreeNode root = new TreeNode(1, null, tn2);

//        List<Integer> integers = preorderTraversal(root);
//        List<Integer> integers = preorderTraversal(null);
//        List<Integer> integers = preorderTraversal(new TreeNode(1));
//        for(Integer i : integers){
//            System.out.println(i);
//        }

        List<Integer> integers = preorderTraversalPlus(root);
        for(Integer i: integers){
            System.out.println(i);
        }
    }
}