It's the Xinrui Ma

Blog

Tag: Tree

Lowest Common Ancestor of a Binary Tree

Posted by in LeetCode on

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary search tree:  root = [3,5,1,6,2,0,8,null,null,7,4]

_______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
             according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the binary tree.

Solution 1:
1. Find the path to specific node p, and q.
2. Compare the path array from beginning, if same, move to next path node, until they didn’t match
3. return the last match node.

Solution 2:

The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.

Construct Binary Tree from Inorder and Postorder Traversal

Posted by in LeetCode on

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

3
   / \
  9  20
    /  \
   15   7

Thought:
Inorder: [left, root, right]
postorder: [left, right, root]

So from each postorder array, we can get the current Root node for the tree, and use that root node, we can find the left subtree for the root, and the right subtree for the root.
Also we can get the postorder sequence by the number of left subtree nodes, and the number of right subtree nodes.

The end condition is we reach a leaf node, we set it’s left and right child to null, and return that node.

Count Univalue Subtrees

Posted by in LeetCode on

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

Example :

Input:  root = [5,1,5,5,5,null,5]

              5
             / \
            1   5
           / \   \
          5   5   5

Output: 4

Solution:

How to print root to leaf path in a binary tree.

Posted by in LeetCode on

Key idea is to use a list or an array, and record the depth of the current node, if it’s a leaf, print the list, otherwise, add/replace the node to the list corresponding places.

Solutoin in JavaScript:

Solution in Java:

112. Path Sum

Posted by in LeetCode on

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution:

Solution 2:

Symmetric Tree

Posted by in LeetCode on

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:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution:
Iteratively:
Use BFS, at each level, check if the array is Symmetric or not:

Recursively:

404. Sum of Left Leaves

Posted by in LeetCode on

Find the sum of all left leaves in a given binary tree.

Example:

Easy one:

Travel through the tree, if one node’s left child is a leave, add to the sum.

Invert a binary tree in Java and JavaScript

Posted by in LeetCode on

to

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.