给定一个二叉树,返回它的 前序 遍历。
示例:
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
算法
swift
树结构
// Definition for a binary tree node.
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
- 递归
/**
前序遍历:中左右
递归
*/
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
helper(root, &result)
return result
}
func helper(_ node: TreeNode?, _ result: inout [Int]) {
guard node != nil else {
return
}
result.append(node!.val)
helper(node?.left, &result)
helper(node?.right, &result)
}
- 迭代
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
if root == nil {
return result
}
// 辅助栈
var stack = [TreeNode]()
stack.append(root!)
while !stack.isEmpty {
let current = stack.popLast()
if current != nil {
result.append(current!.val)
} else {
continue
}
// 栈:先入后出。入栈时先入右,后入左
if current?.right != nil {
stack.append(current!.right!)
}
if current?.left != nil {
stack.append(current!.left!)
}
}
return result
}
Java
- 递归
class Solution {
public List<Integer> preorderTraversal(final TreeNode root) {
final List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
helper(root, result);
return result;
}
public void helper(TreeNode node, final List result) {
if (node == null) {
return;
}
result.add(node.val);
helper(node.left, result);
helper(node.right, result);
}
}
- 迭代
/**
* 迭代方法
* @param root
* @return
*/
public List<Integer> preorderTraversal(final TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return result;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
result.add(current.val);
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
return result;
}
GitHub:https://github.com/huxq-coder/LeetCode
欢迎star
网友评论