Given a binary tree, return the preorder traversal of its nodes’ values.
Example:
1 2 3 4 5 6 7 8
Input: [1,null,2,3] 1 \ 2 / 3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
分析
先序遍历,可以当做例题。
解决方案1(Python)
递归版本。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defpreorderTraversal(self, root: Optional[TreeNode]) -> List[int]: result = [] defpreOrder(root): if root: result.append(root.val) preOrder(root.left) preOrder(root.right) preOrder(root) return result
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ classSolution{ public List<Integer> preorderTraversal(TreeNode root){ ArrayList<Integer> result = new ArrayList<Integer>(); preOrder(root, result); return result; } privatevoidpreOrder(TreeNode root, ArrayList<Integer> result){ if (root == null) { return; } result.add(root.val); preOrder(root.left, result); preOrder(root.right, result); } }
解决方案3(golang)
递归版本。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ funcpreorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } result := []int{} result = append(result, root.Val) left := append(result, preorderTraversal(root.Left)...) returnappend(left, preorderTraversal(root.Right)...) }