aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-19 17:57:15 -0700
committerJack Sangdahl <[email protected]>2024-12-19 17:57:15 -0700
commit2199755f6718c0f5489248efa46768ca0da7b430 (patch)
tree36bd0cfd9c0358b8c42b46a1018a3aebbef23088
parent77714a237b951c7faf0d28e135401246c1805346 (diff)
downloadleetcode-2199755f6718c0f5489248efa46768ca0da7b430.tar.gz
leetcode-2199755f6718c0f5489248efa46768ca0da7b430.zip
2415. reverse odd levels of binary tree
-rw-r--r--reverse_odd_levels_bt.c41
-rw-r--r--reverse_odd_levels_bt.py43
2 files changed, 84 insertions, 0 deletions
diff --git a/reverse_odd_levels_bt.c b/reverse_odd_levels_bt.c
new file mode 100644
index 0000000..834bca5
--- /dev/null
+++ b/reverse_odd_levels_bt.c
@@ -0,0 +1,41 @@
+// 2415. Reverse Odd Levels of Binary Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a perfect binary tree, reverse the node values at each
+ * odd level of the tree. return the root of the reversed tree. a binary tree is
+ * perfect if all parent nodes have two children and all leaves are on the same
+ * level. the level of a node is the number of edges along the path between it
+ * and the root node.
+ */
+
+void dfs(struct TreeNode *node1, struct TreeNode *node2, int level) {
+ if (!node1 || !node2)
+ return;
+ if (!(level % 2)) {
+ int tmp = node1->val;
+ node1->val = node2->val;
+ node2->val = tmp;
+ }
+ dfs(node1->left, node2->right, level + 1);
+ dfs(node1->right, node2->left, level + 1);
+}
+
+struct TreeNode *reverseOddLevels(struct TreeNode *root) {
+ dfs(root->left, root->right, 0);
+ return root;
+}
+
+int main() {
+ struct TreeNode *root = treenode_create(2);
+ root->left = treenode_create(3);
+ root->right = treenode_create(5);
+ root->left->left = treenode_create(8);
+ root->left->right = treenode_create(13);
+ root->right->left = treenode_create(21);
+ root->right->right = treenode_create(34);
+ struct TreeNode *rol = reverseOddLevels(root);
+ treenode_print(rol);
+ treenode_free(root);
+ treenode_free(rol);
+}
diff --git a/reverse_odd_levels_bt.py b/reverse_odd_levels_bt.py
new file mode 100644
index 0000000..f69f171
--- /dev/null
+++ b/reverse_odd_levels_bt.py
@@ -0,0 +1,43 @@
+# 2415. Reverse Odd Levels of Binary Tree
+
+"""
+given the 'root' of a perfect binary tree, reverse the node values at each
+odd level of the tree. return the root of the reversed tree. a binary tree is
+perfect if all parent nodes have two children and all leaves are on the same
+level. the level of a node is the number of edges along the path between it
+and the root node.
+"""
+
+
+# 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 reverseOddLevels(self, root):
+ """
+ :type root: Optional[TreeNode]
+ :rtype: Optional[TreeNode]
+ """
+
+ def dfs(node1, node2, level):
+ if not node1 or not node2:
+ return
+ if level % 2 != 0:
+ node1.val, node2.val = node2.val, node1.val
+ dfs(node1.left, node2.right, level + 1)
+ dfs(node1.right, node2.left, level + 1)
+
+ dfs(root.left, root.right, 1)
+ return root
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.reverseOddLevels(root=[2, 3, 5, 8, 13, 21, 34]))
+ print(obj.reverseOddLevels(root=[7, 13, 11]))
+ print(obj.reverseOddLevels(root=[0, 1, 2, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]))