Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 Thoughts What if a node is NULL? A NULL has no children, so how to iterate deeper into the tree? Solution // Attempt // class Solution { // public: void swapNodes(*leftNode, *rightNode) { *temp = *leftNode; *leftNode = *rightNode; *rightNode = temp; return; } TreeNode* invertTree(TreeNode* root) { if (root == NULL) return invertTree(root->left) } }; Solution C++
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Example 1 Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2 Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 ``` ### Follow-up What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?
Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1 Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2 Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42 Solution Python
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Note Bonus points if you could solve it both recursively and iteratively. Solution Resursive: # Definition for a binary tree node.
Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true Example 2: Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: false Example 3: Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false Solution # Definition for a binary tree node.
Given a linked list, swap every two adjacent nodes and return its head. Example Given 1->2->3->4, you should return the list as 2->1->4->3. Note Your algorithm should use only constant extra space. You may not modify the values in the list’s nodes, only nodes itself may be changed. Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def swapPairs(self, head): """ :type head: ListNode :rtype: ListNode """ # https://www.
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.
Given a binary tree, return the preorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,2,3] Follow-up Recursive solution is trivial, could you do it iteratively? Solution # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def preorderTraversal_1(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] return [root.
Given a binary tree, return the postorder traversal of its nodes’ values. Example Input: [1,null,2,3] 1 \ 2 / 3 Output: [3,2,1] Follow-up Recursive solution is trivial, could you do it iteratively? Solution Recursive👇 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ def traverse(node): if node == None: return [] return traverse(node.