上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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:
int longestZigZag(TreeNode* root) {
}
};
cpp 解法, 执行用时: 152 ms, 内存消耗: 91.8 MB, 提交时间: 2022-12-11 12:44:50
/**
* 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:
int maxAns;
/* 0 => left, 1 => right */
void dfs(TreeNode* o, bool dir, int len) {
maxAns = max(maxAns, len);
if (!dir) {
if (o->left) dfs(o->left, 1, len + 1);
if (o->right) dfs(o->right, 0, 1);
} else {
if (o->right) dfs(o->right, 0, len + 1);
if (o->left) dfs(o->left, 1, 1);
}
}
int longestZigZag(TreeNode* root) {
if (!root) return 0;
maxAns = 0;
dfs(root, 0, 0);
dfs(root, 1, 0);
return maxAns;
}
};
java 解法, 执行用时: 9 ms, 内存消耗: 51.7 MB, 提交时间: 2022-12-11 12:44:32
/**
* 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 {
int maxAns;
public int longestZigZag(TreeNode root) {
if (root == null) {
return 0;
}
maxAns = 0;
dfs(root, false, 0);
dfs(root, true, 0);
return maxAns;
}
public void dfs(TreeNode o, boolean dir, int len) {
maxAns = Math.max(maxAns, len);
if (!dir) {
if (o.left != null) {
dfs(o.left, true, len + 1);
}
if (o.right != null) {
dfs(o.right, false, 1);
}
} else {
if (o.right != null) {
dfs(o.right, false, len + 1);
}
if (o.left != null) {
dfs(o.left, true, 1);
}
}
}
}
python3 解法, 执行用时: 440 ms, 内存消耗: 61.8 MB, 提交时间: 2022-12-11 12:44: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
# 深度优先遍历
class Solution:
def longestZigZag(self, root: TreeNode) -> int:
maxans = 0
def dfs(o, direction, length):
if not o:
return
nonlocal maxans
maxans = max(maxans, length)
if direction == 0:
dfs(o.left, 1, length + 1)
dfs(o.right, 0, 1)
else:
dfs(o.right, 0, length + 1)
dfs(o.left, 1, 1)
dfs(root, 0, 0)
dfs(root, 1, 0)
return maxans
python3 解法, 执行用时: 372 ms, 内存消耗: 28.9 MB, 提交时间: 2022-12-11 12:43:54
# 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 longestZigZag(self, root: TreeNode) -> int:
f, g = collections.defaultdict(int), collections.defaultdict(int)
q = collections.deque([(root, None)])
while len(q) > 0:
node, parent = q.popleft()
if parent:
if parent.left == node:
f[node] = g[parent] + 1
else:
g[node] = f[parent] + 1
if node.left:
q.append((node.left, node))
if node.right:
q.append((node.right, node))
maxans = 0
for _, val in f.items():
maxans = max(maxans, val)
for _, val in g.items():
maxans = max(maxans, val)
return maxans
java 解法, 执行用时: 82 ms, 内存消耗: 49.6 MB, 提交时间: 2022-12-11 12:43:31
/**
* 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 {
Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();
Queue<TreeNode[]> q = new LinkedList<TreeNode[]>();
public int longestZigZag(TreeNode root) {
dp(root);
int maxAns = 0;
for (TreeNode u : f.keySet()) {
maxAns = Math.max(maxAns, Math.max(f.get(u), g.get(u)));
}
return maxAns;
}
public void dp(TreeNode o) {
f.put(o, 0);
g.put(o, 0);
q.offer(new TreeNode[]{o, null});
while (!q.isEmpty()) {
TreeNode[] y = q.poll();
TreeNode u = y[0], x = y[1];
f.put(u, 0);
g.put(u, 0);
if (x != null) {
if (x.left == u) {
f.put(u, g.get(x) + 1);
}
if (x.right == u) {
g.put(u, f.get(x) + 1);
}
}
if (u.left != null) {
q.offer(new TreeNode[]{u.left, u});
}
if (u.right != null) {
q.offer(new TreeNode[]{u.right, u});
}
}
}
}
cpp 解法, 执行用时: 268 ms, 内存消耗: 139.6 MB, 提交时间: 2022-12-11 12:43:16
/**
* 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:
unordered_map <TreeNode*, int> f, g;
queue <pair <TreeNode *, TreeNode *>> q;
void dp(TreeNode *o) {
f[o] = g[o] = 0;
q.push({o, nullptr});
while (!q.empty()) {
auto y = q.front(); q.pop();
auto x = y.second, u = y.first;
f[u] = g[u] = 0;
if (x) {
if (x->left == u) f[u] = g[x] + 1;
if (x->right == u) g[u] = f[x] + 1;
}
if (u->left) q.push({u->left, u});
if (u->right) q.push({u->right, u});
}
}
int longestZigZag(TreeNode* root) {
dp(root);
int maxAns = 0;
for (const auto &u: f) maxAns = max(maxAns, max(u.second, g[u.first]));
return maxAns;
}
};
