Qi

Cogito ergo sum

0%

leetcode 144 Solution

发表于 更新于 分类于 132 1 分钟

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package com.demo.s144;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的前序遍历
 *
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //定义结果list
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        //定义队列 遍历时存放当前节点用
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while(stack.size() != 0 || node!= null) {
            while(node != null) {
                res.add(node.val);
                //先当前节点
                stack.push(node);
                //后left节点
                node = node.left;
            }
            //最后右节点
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}