Press "Enter" to skip to content

Posts tagged as “traversal”

花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

  • 1 <= pre.length == post.length <= 30
  • pre[] and post[] are both permutations of 1, 2, ..., pre.length.
  • It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Solution: Recursion

pre = [(root) (left-child) (right-child)]

post = [(left-child) (right-child) (root)]

We need to recursively find the first node in pre.left-child from post.left-child

e.g.

pre = [(1), (2,4,5), (3,6,7)]

post = [(4,5,2), (6,7,3), (1)]

First element of left-child is 2 and the length of it is 3.

root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))

Time complexity: O(n^2)

Space complexity: O(n)

Time complexity: O(n^2)

Space complexity: O(n)

Time complexity: O(n)

 

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

 

For example, given a 3-ary tree:

 

Return its postorder traversal as: [5,6,3,2,4,1].

 

Note: Recursive solution is trivial, could you do it iteratively?

 

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 513. Find Bottom Left Tree Value

题目大意:给你一棵树,返回左下角(最后一行最左面)的节点的值。

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Example 2: 

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

Python3

 

 

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

Solution 2:

Solution 3:

 

花花酱 LeetCode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

Solution 1: BFS O(n)

Solution 2: DFS O(n)