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
Trees can be traversed to:
- Find the kth smallest element
- Check whether it is a valid BST
Leetcode 226. Invert Binary Tree
Python
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# Base case
# O(n)
if not root:
return None
# The swapping is an O(1) operation, but it's called n times
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
# Total: O(n)
return root
C++
Leetcode 199. Binary Tree Right Side View
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
"""
Perform a level order traversal of a binary tree and return the values in a nested list.
Each sublist represents one level of the tree.
"""
if not root:
return []
output = []
current_level = deque([root])
while current_level:
level_size = len(current_level)
for i in range(level_size):
node = current_level.popleft()
if i==level_size-1:
output.append(node.val)
if node.left:
current_level.append(node.left)
if node.right:
current_level.append(node.right)
return output/**
* 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:
void _rightSideView(TreeNode* curr, vector<int>& soln, unordered_map<int, int>& marked, int height) {
if(!curr) return;
if(!marked[height]) {
marked[height] = 1;
soln.push_back(curr->val);
}
_rightSideView(curr->right, soln, marked, height+1);
_rightSideView(curr->left, soln, marked, height+1);
}
vector<int> rightSideView(TreeNode* root) {
vector<int> soln;
unordered_map<int, int> marked;
_rightSideView(root, soln, marked, 1);
return soln;
}
};