华为OD机试 - 二叉树计算（Java & JS & Python & C & C++）

题目描述：

给定一个二叉树的根节点 root ，返回树的节点值的前序遍历。

示例：

输入: root = [1,null,2,3]

输出: [1,2,3]

提示：

树中节点的数目在范围 [0, 100] 内

-100 <= Node.val <= 100

解法1：递归

Java版：

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

JavaScript版：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    preorder(root, res);
    return res;
};
 
function preorder(node, res) {
    if (node === null) return;
    res.push(node.val);
    preorder(node.left, res);
    preorder(node.right, res);
}

Python版：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.preorder(root, res)
        return res
 
    def preorder(self, node, res):
        if not node:
            return
        res.append(node.val)
        self.preorder(node.left, res)
        self.preorder(node.right, res)

解法2：迭代

Java版：

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

JavaScript版：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    if (root === null) return res;
 
    let stack = [root];
 
    while (stack.length > 0) {
        let node = stack.pop();
        res.push(node.val);
        if (node.right !== null) stack.push(node.right);
        if (node.left