二叉树的遍历

前序遍历 采用递归

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

前序遍历采用迭代

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        nodeStack.push(root);
        List<Integer> list = new ArrayList<Integer>();
        
        while(nodeStack.size() != 0 ){
            TreeNode node = nodeStack.pop();
            list.add(node.val);            
            if(node.right != null)
                nodeStack.push(node.right);
            if(node.left != null)
                nodeStack.push(node.left);
        }
        
        return list;
        
    }
}