花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

<b>Input:</b>

/ \

3 2

/ \ \

5 3 9

<b>Output:</b> [1, 3, 9]

Solution 1: Inorder traversal + depth info

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> ans;

inorder(root, 0, ans);

return ans;

}

private:

void inorder(TreeNode* root, int d, vector<int>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back(INT_MIN);

inorder(root->left, d + 1, ans);

ans[d] = max(ans[d], root->val);

inorder(root->right, d + 1, ans);

}

};

Python3

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def largestValues(self, root):

def inorder(root, d, ans):

if not root: return ans

if len(ans) <= d: ans += [float('-inf')]

inorder(root.left, d + 1, ans)

if root.val > ans[d]: ans[d] = root.val

inorder(root.right, d + 1, ans)

return ans

return inorder(root, 0, [])

花花酱 LeetCode 513. Find Bottom Left Tree Value

By zxi on March 5, 2018

题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。

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:

Input:

/ \

1 3

Output:

Example 2:

Input:

/ \

2 3

/ / \

4 5 6

Output:

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.

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int max_row = -1;

int ans;

dfs(root, 0, max_row, ans);

return ans;

}

private:

void inorder(TreeNode* root, int row, int& max_row, int& ans) {

if (root == nullptr) return;

inorder(root->left, row + 1, max_row, ans);

if (row > max_row) {

ans = root->val;

max_row = row;

}

inorder(root->right, row + 1, max_row, ans);

}

};

Python3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def inorder(self, root, row):

if not root: return

self.inorder(root.left, row + 1)

if row > self.max_row:

self.max_row, self.ans = row, root.val

self.inorder(root.right, row + 1)

def findBottomLeftValue(self, root):

self.ans, self.max_row = 0, -1

self.inorder(root, 0)

return self.ans

花花酱 LeetCode 145. Binary Tree Postorder Traversal

By zxi on September 8, 2017

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:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

Posts tagged as “inorder”

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

花花酱 LeetCode 513. Find Bottom Left Tree Value

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Solution 1:

Solution 2:

Solution 3: