diff options
author | Jack Sangdahl <[email protected]> | 2024-12-19 17:57:15 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-19 17:57:15 -0700 |
commit | 2199755f6718c0f5489248efa46768ca0da7b430 (patch) | |
tree | 36bd0cfd9c0358b8c42b46a1018a3aebbef23088 | |
parent | 77714a237b951c7faf0d28e135401246c1805346 (diff) | |
download | leetcode-2199755f6718c0f5489248efa46768ca0da7b430.tar.gz leetcode-2199755f6718c0f5489248efa46768ca0da7b430.zip |
2415. reverse odd levels of binary tree
-rw-r--r-- | reverse_odd_levels_bt.c | 41 | ||||
-rw-r--r-- | reverse_odd_levels_bt.py | 43 |
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])) |