Given the root
of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [1,2,3]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
[0, 100]
.-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
We first visit the root node, then recursively traverse the left and right subtrees.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.
# 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
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root):
if root is None:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)
ans = []
dfs(root)
return ans
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
dfs(root);
return ans;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
ans.add(root.val);
dfs(root.left);
dfs(root.right);
}
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
if (!root) {
return;
}
ans.push_back(root->val);
dfs(root->left);
dfs(root->right);
};
dfs(root);
return ans;
}
};
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) (ans []int) {
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
ans = append(ans, root.Val)
dfs(root.Left)
dfs(root.Right)
}
dfs(root)
return
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
const ans: number[] = [];
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
ans.push(root.val);
dfs(root.left);
dfs(root.right);
};
dfs(root);
return ans;
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
if root.is_none() {
return;
}
let node = root.as_ref().unwrap().borrow();
ans.push(node.val);
Self::dfs(&node.left, ans);
Self::dfs(&node.right, ans);
}
pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans = vec![];
Self::dfs(&root, &mut ans);
ans
}
}
The idea of using a stack to implement non-recursive traversal is as follows:
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
# 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
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if root is None:
return ans
stk = [root]
while stk:
node = stk.pop()
ans.append(node.val)
if node.right:
stk.append(node.right)
if node.left:
stk.append(node.left)
return ans
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(root);
while (!stk.isEmpty()) {
TreeNode node = stk.pop();
ans.add(node.val);
if (node.right != null) {
stk.push(node.right);
}
if (node.left != null) {
stk.push(node.left);
}
}
return ans;
}
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) {
return ans;
}
stack<TreeNode*> stk;
stk.push(root);
while (stk.size()) {
auto node = stk.top();
stk.pop();
ans.push_back(node->val);
if (node->right) {
stk.push(node->right);
}
if (node->left) {
stk.push(node->left);
}
}
return ans;
}
};
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) (ans []int) {
if root == nil {
return
}
stk := []*TreeNode{root}
for len(stk) > 0 {
node := stk[len(stk)-1]
stk = stk[:len(stk)-1]
ans = append(ans, node.Val)
if node.Right != nil {
stk = append(stk, node.Right)
}
if node.Left != nil {
stk = append(stk, node.Left)
}
}
return
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
const ans: number[] = [];
if (!root) {
return ans;
}
const stk: TreeNode[] = [root];
while (stk.length) {
const { left, right, val } = stk.pop();
ans.push(val);
right && stk.push(right);
left && stk.push(left);
}
return ans;
}
Morris traversal does not require a stack, and its space complexity is $O(1)$. The core idea is:
Traverse the binary tree nodes,
root
is empty, add the current node value to the result list $ans$, and update the current node to root.right
.root
is not empty, find the rightmost node pre
of the left subtree (which is the predecessor of the root
node in inorder traversal):
pre
is empty, add the current node value to the result list $ans$, then point the right subtree of the predecessor node to the current node root
, and update the current node to root.left
.pre
is not empty, point the right subtree of the predecessor node to null (i.e., disconnect pre
and root
), and update the current node to root.right
.The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. The space complexity is $O(1)$.
# 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
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
while root:
if root.left is None:
ans.append(root.val)
root = root.right
else:
prev = root.left
while prev.right and prev.right != root:
prev = prev.right
if prev.right is None:
ans.append(root.val)
prev.right = root
root = root.left
else:
prev.right = None
root = root.right
return ans
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
while (root != null) {
if (root.left == null) {
ans.add(root.val);
root = root.right;
} else {
TreeNode prev = root.left;
while (prev.right != null && prev.right != root) {
prev = prev.right;
}
if (prev.right == null) {
ans.add(root.val);
prev.right = root;
root = root.left;
} else {
prev.right = null;
root = root.right;
}
}
}
return ans;
}
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
while (root) {
if (!root->left) {
ans.push_back(root->val);
root = root->right;
} else {
TreeNode* prev = root->left;
while (prev->right && prev->right != root) {
prev = prev->right;
}
if (!prev->right) {
ans.push_back(root->val);
prev->right = root;
root = root->left;
} else {
prev->right = nullptr;
root = root->right;
}
}
}
return ans;
}
};
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) (ans []int) {
for root != nil {
if root.Left == nil {
ans = append(ans, root.Val)
root = root.Right
} else {
prev := root.Left
for prev.Right != nil && prev.Right != root {
prev = prev.Right
}
if prev.Right == nil {
ans = append(ans, root.Val)
prev.Right = root
root = root.Left
} else {
prev.Right = nil
root = root.Right
}
}
}
return
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
const ans: number[] = [];
while (root) {
const { left, right, val } = root;
if (!left) {
ans.push(val);
root = right;
} else {
let prev = left;
while (prev.right && prev.right != root) {
prev = prev.right;
}
if (!prev.right) {
ans.push(val);
prev.right = root;
root = root.left;
} else {
prev.right = null;
root = root.right;
}
}
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。