LeetCode.Binary Tree

A binary tree consists of:

1. Node element;
2. Pointer to the child node Left;
3. Pointer to another child node Right.

LeetCode tree representation:

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

leetcode104. Maximum Depth of Binary Tree

#

int maxDepth(TreeNode* root) {
	if(root==nullptr){
		return 0;
	}
	return max(maxDepth(root->left),maxDepth(root->right))+1;
}

• Recursively calculate the depth of the left and right subtrees first #Recursion
• max() returns the maximum depth + 1

leetcode226. Invert Binary Tree

#

TreeNode* invertTree(TreeNode* root) {
	if(root==nullptr){
		return nullptr;
	}
	TreeNode* temp;
	temp=root->left;
	root->left=root->right;
	root->right=temp;
	invertTree(root->left);
	invertTree(root->right);
	return root;
}

Consider traversing the binary tree recursively and swapping the left/right child nodes of each node to generate a mirror image of the binary tree.

• Time Complexity: O(n)
• Space Complexity: O(n)

leetcode101. Symmetric Tree

#

bool isSymmetric(TreeNode* root) {
	if(root==nullptr){
		return true;
	}
	return isMirror(root->left,root->right);
}
bool isMirror(TreeNode* root1,TreeNode* root2){
	if(root1==nullptr&&root2==nullptr){
		return true;
	}
	if(root1==nullptr||root2==nullptr||root1->val!=root2->val){
		return false;
	}
	return(isMirror(root1->left,root2->right)&&isMirror(root1->right,root2->left));
 }

• Time Complexity: O(n)
• Space Complexity: O(n)

Function isSymmetric() :

• Special case handling: If the root node is null, return true directly.
• Return value: The result of isMirror(root->left, root->right).

Function isMirror():

• First, check if the current left and right nodes satisfy the symmetry condition.
• Then, check if the sub-nodes L.left and R.right are symmetric, and L.right and R.left are symmetric. #Recursion ![[SymmetricTree.png|697]]