It's the Xinrui Ma

Blog

Tag: Binary Tree

Binary tree preorder, inorder, postorder traverse iteratively in JavaScript

Posted by in LeetCode on

preOrder:

Inorder:

Postorder:

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.

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:

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: