preOrder 二叉树先序遍历

慢慢练脑子

留意下非递归方法，存stack前先检测下是否为null。

1. 来源：

题： leetcode

2. 解法：

2.1 递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        helper(root, result);
        
        return result;
    }
    
    private void helper(TreeNode root, List<Integer> result) {
        
        if(root == null) {
            return;
        }
        
        result.add(root.val);
        helper(root.left, result);
        helper(root.right, result);
        
    }
}

2.1 非递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> result = new ArrayList<>();
        
        Stack<TreeNode> nodeStack = new Stack<>();
        if(root == null) {
            return result;
        }
        
        nodeStack.add(root);
        while(!nodeStack.isEmpty()) {
            TreeNode top = nodeStack.pop();
            
            result.add(top.val);
            if(top.right != null) {
                nodeStack.add(top.right);
            }
            if(top.left != null) {
                nodeStack.add(top.left);
            }
        }
        
        return result;
        
    }
}