# LeetCode-Tree

[TOC]   ``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
``````

## 遍历求解

### 572. Subtree of Another Tree (Easy) Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

#### Solution

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (nullptr == s && nullptr == t) {
return true;
}
if (nullptr == s || nullptr == t) {
return false;
}
return isIdentical(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}
private:
bool isIdentical(TreeNode* s, TreeNode* t) {
if (nullptr == s && nullptr == t) {
return true;
}
if (nullptr == s || nullptr == t) {
return false;
}
if (s->val != t->val) {
return false;
}
return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
}
};
``````

### 965. Univalued Binary Tree (Easy) A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Easy的题, 直接遍历就好了

``````class Solution {
public:
bool isUnivalTree(TreeNode* root) {
int rootVal = root->val;
return isUnivalTree(root, rootVal);
}
private:
bool isUnivalTree(TreeNode* root, int rootVal) {
if (nullptr == root) {
return true;
}
if (root->val != rootVal) {
return false;
}
return isUnivalTree(root->left, rootVal) && isUnivalTree(root->right, rootVal);
}
};
``````

## collecting nodes

### 107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). 本来打算按层遍历. 只要记录节点深度就可以

``````class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ret;
levelTravel(root, ret, 0);
reverse(ret.begin(), ret.end());
return ret;
}
private:
void levelTravel(TreeNode* root, vector<vector<int>>& ans, int level) {
if (nullptr == root) {
return;
}
if (level >= ans.size()) {
ans.push_back(vector<int>());
}
ans[level].push_back(root->val);
levelTravel(root->left, ans, level+1);
levelTravel(root->right, ans, level+1);
}
};
``````

### 429. N-ary Tree Level Order Traversal (Medium)

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

``````/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret;
levelOrder(root, ret, 0);
return ret;
}
private:
void levelOrder(Node* root, vector<vector<int>>& ret, int level) {
if (nullptr == root) {
return;
}
if (level >= ret.size()) {
ret.push_back(vector<int>());
}
ret[level].push_back(root->val);
for (auto p: root->children) {
levelOrder(p, ret, level+1);
}
}
};
``````

### 872. Leaf-Similar Trees (Easy) Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence. Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

``````class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> seq1, seq2;
leafTravel(root1, seq1);
leafTravel(root2, seq2);
if (seq1.size() != seq2.size()) {
return false;
}
for (int idx = 0; idx < seq1.size(); ++idx) {
if (seq1[idx] != seq2[idx]) {
return false;
}
}
return true;
}
private:
void leafTravel(TreeNode* root, vector<int>& leafSeq) {
if (nullptr == root) {
return;
}
if (isLeaf(root)) {
leafSeq.push_back(root->val);
}
leafTravel(root->left, leafSeq);
leafTravel(root->right, leafSeq);
}
bool isLeaf(TreeNode* p) {
if (nullptr == p) {
return false;
}
if (p->left == nullptr && p->right == nullptr) {
return true;
}
return false;
}
};
``````

### 669. Trim a Binary Search Tree (Easy) Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R, bool top=true) {
if (!root) {
return root;
}
root->left = trimBST(root->left, L, R, false);
root->right = trimBST(root->right, L, R, false);
// 左右子节点都是trim后的, 如果当前节点值在合法范围内, 直接直接返回即可
if (root->val >= L && root->val <= R) {
return root;
}
TreeNode* ret = nullptr;
// 根据当前节点在给定范围的方向, 返回某一个已经trim的子树
if (root->val < L) {
ret = root->right;
}
else {
ret = root->left;
}
if (!top) {
delete root;
}
return ret;

}

};
``````

### 1325. Delete Leaves With a Given Value

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if it's parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you can't).

https://leetcode.com/problems/delete-leaves-with-a-given-value/discuss/484264/JavaC++Python-Recursion-Solution/431234
1.Leetcode doesn't let you call delete on a node.

``````class Solution {
public:
TreeNode* removeLeafNodes(TreeNode* &p, int target) {
if (nullptr == p) {
return p;
}
removeLeafNodes(p->left, target);
removeLeafNodes(p->right, target);
if (!p->left && !p->right && p->val == target) {
// delete p;
p = nullptr;
}
return p;
}
};
``````

### 113. Path Sum II (Medium)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

``````class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ret;
vector<int> path;
if (nullptr == root) {
return ret;
}
dfs(root, ret, path, 0, sum);
return ret;

}
private:
void dfs(TreeNode* p,vector<vector<int>> &ret, vector<int>& path,int c_sum, int sum) {
if (nullptr == p) {
return;
}
c_sum += p->val;
path.push_back(p->val);
if (!p->left && !p->right && c_sum == sum) {
ret.push_back(path);
}
dfs(p->left, ret, path, c_sum, sum);
dfs(p->right, ret, path, c_sum, sum);
path.pop_back();

}
};
``````

### 437. Path Sum III (Easy) You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

``````class Solution {
public:
int pathSum(TreeNode* root, int sum) {
int cnt = 0;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* p = stk.top();
stk.pop();
if (nullptr == p) {
continue;
}
dfs(p, 0, sum, cnt);
stk.push(p->left);
stk.push(p->right);
}

return cnt;
}
private:
void dfs(TreeNode* p, int c_sum, int sum, int &cnt) {
if (nullptr == p) {
return;
}
c_sum += p->val;
if (c_sum == sum) {
++cnt;
}
dfs(p->left, c_sum, sum, cnt);
dfs(p->right, c_sum, sum, cnt);
// dfs(p->left, 0, sum, cnt);
// dfs(p->right, 0, sum, cnt);
}
};
``````

### 257. Binary Tree Paths (Easy) Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

``````class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ret;
vector<int> path;
dfs(root, path, ret);
return ret;
}
private:
void dfs(TreeNode* p, vector<int> &path, vector<string> &ret, bool top=false) {
if (nullptr == p) {
return;
}
path.push_back(p->val);
if (!p->left && !p->right) {

string pathStr = to_string(path);
for (int i = 1; i < path.size(); ++i) {
pathStr += "->" + to_string(path[i]);
}
ret.push_back(pathStr);
// return;
}
dfs(p->left, path, ret);
dfs(p->right, path, ret);
path.pop_back();
}
};
``````

### 235. Lowest Common Ancestor of a Binary Search Tree Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

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).”

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (nullptr == root) {
return nullptr;
}
int v1 = p->val, v2 = q->val;
int minVal = min(v1, v2);
int maxVal = max(v1, v2);
return dfs(root, minVal, maxVal);
}
private:
TreeNode* dfs(TreeNode* p, int minVal, int maxVal) {
if (p->val > maxVal) {
return dfs(p->left, minVal, maxVal);
}
else if (p->val < minVal) {
return dfs(p->right, minVal, maxVal);
}
return p;
}
};
``````

### 449. Serialize and Deserialize BST (Medium) Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

``````class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
ostringstream  ost;
serialize(root, ost);
return ost.str();
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data == "") return nullptr;
istringstream ist(data);
int val;
ist >> val;
TreeNode *root = new TreeNode(val);
while (ist >> val) {
insertBST(root, val);
}
return root;
}
private:
void serialize(TreeNode* p, ostringstream &ost) {
if (nullptr == p) {
return;
}
ost << p->val << " ";
serialize(p->left, ost);
serialize(p->right, ost);
}
void insertBST(TreeNode* p, int val) {
if (p->val > val) {
if (p->left == nullptr) {
p->left = new TreeNode(val);
}
else {
insertBST(p->left, val);
}
}
else {
if (p->right == nullptr) {
p->right = new TreeNode(val);
}
else {
insertBST(p->right, val);
}
}
}
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
`````` 