">- 105. 从前序与中序遍历序列构造二叉树">105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树">106. 从中序与后序遍历序列构造二叉树
- 889. 根据前序和后序遍历构造二叉树">889. 根据前序和后序遍历构造二叉树
- 108. 将有序数组转换为二叉搜索树">108. 将有序数组转换为二叉搜索树
- 109. 有序链表转换二叉搜索树">109. 有序链表转换二叉搜索树
- 114. 二叉树展开为链表">114. 二叉树展开为链表
- 617. 合并二叉树">617. 合并二叉树
- 剑指 Offer 37. 序列化二叉树">剑指 Offer 37. 序列化二叉树
- 100. 相同的树">100. 相同的树
- 剑指 Offer 28. 对称的二叉树">剑指 Offer 28. 对称的二叉树
- 剑指 Offer 55 - II. 平衡二叉树">剑指 Offer 55 - II. 平衡二叉树
- 98. 验证二叉搜索树">98. 验证二叉搜索树
- 958. 二叉树的完全性检验">958. 二叉树的完全性检验
- 剑指 Offer 26. 树的子结构">剑指 Offer 26. 树的子结构
- 572. 另一棵树的子树">572. 另一棵树的子树
- 剑指 Offer 27. 二叉树的镜像">剑指 Offer 27. 二叉树的镜像
- 二叉树
- 构造二叉树
- 输出二叉树
- 二叉树的验证
- 二叉树翻转
- 二叉树的深度和直径
一级类目 | 二级类型/题目 | 三级类目/题目 | |
---|---|---|---|
二叉树的遍历 | 144. 二叉树的前序遍历 | ||
94. 二叉树的中序遍历 | |||
145. 二叉树的后序遍历 | |||
剑指 Offer 32 - I. 从上到下打印二叉树 | |||
剑指 Offer 32 - II. 从上到下打印二叉树 II | |||
剑指 Offer 32 - III. 从上到下打印二叉树 III | |||
107. 二叉树的层序遍历 II | |||
面试题34. 二叉树中和为某一值的路径 | |||
构造二叉树 |
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
889. 根据前序和后序遍历构造二叉树
108. 将有序数组转换为二叉搜索树
109. 有序链表转换二叉搜索树
114. 二叉树展开为链表
617. 合并二叉树
剑指 Offer 37. 序列化二叉树
100. 相同的树
剑指 Offer 28. 对称的二叉树
剑指 Offer 55 - II. 平衡二叉树
98. 验证二叉搜索树
958. 二叉树的完全性检验
剑指 Offer 26. 树的子结构
572. 另一棵树的子树
剑指 Offer 27. 二叉树的镜像
| | | | | 156.上下翻转二叉树 | |
二叉树
二叉树的遍历
144. 二叉树的前序遍历
解法一:递归
class Solution {
public:
vector<int> res;
void preOrder(TreeNode *root) {
if (!root)return;
res.push_back(root->val);
preOrder(root->left);
preOrder(root->right);
}
vector<int> preorderTraversal(TreeNode *root) {
preOrder(root);
return res;
}
};
解法二:使用栈迭代
class Solution {
public:
vector<int> res;
// root ,left,right
vector<int> preorderTraversal(TreeNode *root) {
if (!root)return res;
stack<TreeNode *> st;
TreeNode *node = root;
while (!st.empty() || node) {
while (node) {
res.emplace_back(node->val);
st.emplace(node);
node = node->left;
}
node = st.top();
st.pop();
node = node->right;
}
return res;
}
};
94. 二叉树的中序遍历
解法一
class Solution {
public:
vector<int> res;
void inorder(TreeNode *root) {
if (!root)return;
inorder(root->left);
res.push_back(root->val);
inorder(root->right);
}
vector<int> inorderTraversal(TreeNode *root) {
inorder(root);
return res;
}
};
解法二
class Solution {
public:
vector<int> res;
// root ,left,right
vector<int> inorderTraversal(TreeNode *root) {
if (!root)return res;
stack<TreeNode *> stack;
while (root || !stack.empty()) {
while (root) {
stack.emplace(root);
root = root->left;
}
root = stack.top();
stack.pop();
res.emplace_back(root->val);
root = root->right;
}
return res;
}
};
145. 二叉树的后序遍历
解法一:
class Solution {
public:
vector<int> res;
void postOrder(TreeNode *root) {
if (!root)return;
postOrder(root->left);
postOrder(root->right);
res.emplace_back(root->val);
}
//left right root
vector<int> postorderTraversal(TreeNode *root) {
postOrder(root);
return res;
}
};
剑指 Offer 32 - I. 从上到下打印二叉树
```cpp class Solution { public: vector
res; vector levelOrder(TreeNode *root) { if (root == nullptr)
{
return res;
}
queue<TreeNode *> queue;
queue.push(root);
while (!queue.empty())
{
int size = queue.size();
for (int i = 0; i < size; i++)
{
TreeNode *tmp = queue.front();
res.push_back(tmp->val);
queue.pop();
if (tmp->left)
{
queue.push(tmp->left);
}
if (tmp->right)
{
queue.push(tmp->right);
}
}
}
return res;
} };
<a name="aDF0i"></a>
#### [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)
```cpp
/**
* 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:
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode *root)
{
if (root == nullptr)
{
return res;
}
queue<TreeNode *> queue;
queue.push(root);
while (!queue.empty())
{
int size = queue.size();
vector<int> ans;
for (int i = 0; i < size; i++)
{
TreeNode *tmp = queue.front();
ans.push_back(tmp->val);
queue.pop();
if (i == size - 1)
{
res.push_back(ans);
}
if (tmp->left)
{
queue.push(tmp->left);
}
if (tmp->right)
{
queue.push(tmp->right);
}
}
}
return res;
}
};
剑指 Offer 32 - III. 从上到下打印二叉树 III
class Solution
{
public:
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode *root)
{
if (!root)
{
return res;
}
queue<TreeNode *> queue;
queue.push(root);
int count = 1;
while (!queue.empty())
{
int size = queue.size();
vector<int> ans;
for (int i = 0; i < size; i++)
{
TreeNode *node = queue.front();
ans.push_back(node->val);
queue.pop();
if (i == size - 1)
{
if (!(count & 1))
{
reverse(ans.begin(), ans.end());
}
res.push_back(ans);
}
if (node->left)
{
queue.push(node->left);
}
if (node->right)
{
queue.push(node->right);
}
}
count += 1;
}
return res;
}
};
107. 二叉树的层序遍历 II
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
vector<vector<int>> res;
vector<vector<int>> levelOrderBottom(TreeNode *root)
{
if (!root)
{
return res;
}
queue<TreeNode *> queue;
queue.push(root);
while (!queue.empty())
{
int size = queue.size();
vector<int> ans;
for (int i = 0; i < size; i++)
{
TreeNode *node = queue.front();
ans.push_back(node->val);
queue.pop();
if (i == size - 1)
{
res.push_back(ans);
}
if (node->left)
{
queue.push(node->left);
}
if (node->right)
{
queue.push(node->right);
}
}
}
reverse(res.begin(),res.end());
return res;
}
};
面试题34. 二叉树中和为某一值的路径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int target) {
dfs(root,target);
return res;
}
void dfs(TreeNode* root,int target){
if(root==nullptr){
return;
}
target-=root->val;
path.push_back(root->val);
if(target==0&&root->left==nullptr&&root->right==nullptr){
res.push_back(path);
}else {
dfs(root->left,target);
dfs(root->right,target);
}
path.pop_back();
}
};
构造二叉树
105. 从前序与中序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> index;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int n = inorder.size();
for (int i = 0; i < n; i++) {
index[inorder[i]] = i;
}
return myselfBuild(preorder, inorder, 0, n - 1, 0, n - 1);
}
// 根 [左子树遍历结果] [右子树遍历结果]
// [左子树遍历结果] 根 [右子树遍历结果]
TreeNode *myselfBuild(vector<int> &preorder, vector<int> &inorder, int preorder_left,
int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
int inorder_root = index[preorder[preorder_left]];
TreeNode *root = new TreeNode(inorder[inorder_root]);
int size_left_subtree = inorder_root - inorder_left;
root->left = myselfBuild(preorder,
inorder,
preorder_left + 1,
preorder_left + size_left_subtree,
inorder_left, inorder_root - 1);
root->right = myselfBuild(preorder,
inorder,
preorder_left + size_left_subtree + 1,
preorder_right,
inorder_root + 1,
inorder_right
);
return root;
}
};
106. 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> index;
// 不要像105那样将数组也递归 ,容易stackoverflow ,使用一个全局代替;
vector<int> post;
TreeNode *buildMySelf(int postorder_left, int postorder_right,
int inorder_left, int inorder_right) {
if (postorder_left > postorder_right || inorder_left > inorder_right) {
return nullptr;
}
int root_val = post[postorder_right];
int inorder_root = index[root_val];
TreeNode *root = new TreeNode(root_val);
int size_left_tree = inorder_root - inorder_left;
root->left = buildMySelf(
postorder_left,
postorder_left + size_left_tree - 1,
inorder_left,
inorder_root - 1);
root->right = buildMySelf(
postorder_left + size_left_tree,
postorder_right - 1,
inorder_root + 1,
inorder_right);
return root;
}
// 左子树遍历 右子树遍历 根
// 左子树遍历 根 右子树遍历
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
int n = inorder.size();
for (int i = 0; i < n; i++) {
index[inorder[i]] = i;
}
post=postorder;
return buildMySelf(0, n - 1, 0, n - 1);
}
};
889. 根据前序和后序遍历构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 根 左子树遍历 右子树遍历
// 左子树遍历 右子树遍历 根
// 1,2,4,5,3,6,7
// 4,5,2,6,7,3,1
unordered_map<int, int> postorder_index;
vector<int> preorderArr;
TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) {
postorder_index[postorder[i]] = i;
}
preorderArr = preorder;
return buildSubTree(0, n - 1, 0, n - 1);
}
TreeNode *buildSubTree(
int preorder_left, int preorder_right,
int postorder_left, int postorder_right) {
if (preorder_left > preorder_right) { return nullptr; }
TreeNode *root = new TreeNode(preorderArr[preorder_left]);
if (preorder_left == preorder_right) { return root; }
// 先序遍历 第二个元素就是左子树 的根节点,也就是2
// 找到2在后序遍历中的位置 ,后续遍历中2之前全部是左子树部分,这样就可以找到左子树长度;
int post_left_index = postorder_index[preorderArr[preorder_left + 1]];
//左子树长度;
int size_left_subtree = post_left_index - postorder_left + 1;
// 1,2,4,5,3,6,7
// 4,5,2,6,7,3,1
root->left = buildSubTree(
preorder_left + 1,
preorder_left + size_left_subtree,
postorder_left, post_left_index
);
root->right = buildSubTree(
preorder_left + size_left_subtree + 1,
preorder_right,
post_left_index + 1,
postorder_right - 1
);
return root;
}
};
108. 将有序数组转换为二叉搜索树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &nums) {
if (nums.empty()) {
return nullptr;
}
return buildBinaryTree(nums, 0, nums.size() - 1);
}
TreeNode *buildBinaryTree(vector<int> &nums, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = left + ((right - left) >> 1);
TreeNode *root = new TreeNode(nums[mid]);
root->left = buildBinaryTree(nums, left, mid - 1);
root->right = buildBinaryTree(nums, mid + 1, right);
return root;
}
};
109. 有序链表转换二叉搜索树
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
ListNode *getMidNode(ListNode *left, ListNode *right) {
ListNode *fast = left;
ListNode *slow = left;
while (fast != right && fast->next!= right) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
TreeNode *buildSubTree(ListNode *left, ListNode *right) {
if (left == right) {
return nullptr;
}
ListNode *mid = getMidNode(left, right);
TreeNode *root = new TreeNode(mid->val);
root->left = buildSubTree(left, mid);
root->right = buildSubTree(mid->next, right);
return root;
}
TreeNode *sortedListToBST(ListNode *head) {
if (head == nullptr) {
return nullptr;
}
return buildSubTree(head, nullptr);
}
};
114. 二叉树展开为链表
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
while(root){
if(!root->left){
root=root->right;
}else {
TreeNode *prev=root->left;
while(prev->right){
prev=prev->right;
}
prev->right=root->right; //将右子树嫁接过来
root->right=root->left;
root->left=nullptr;
root=root->right;
}
}
}
};
617. 合并二叉树
在原来的一个树上做合并操作
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(!root1){
return root2;
}
if(!root2){return root1;}
root1->val+=root2->val;
root1->left=mergeTrees(root1->left,root2->left);
root1->right=mergeTrees(root1->right,root2->right);
return root1;
}
在一棵新树上做合并操作
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(!root1){
return root2;
}
if(!root2){return root1;}
TreeNode* tmp=new TreeNode(root1->val+root2->val);
tmp->left=mergeTrees(root1->left,root2->left);
tmp->right=mergeTrees(root1->right,root2->right);
return tmp;
}
输出二叉树
剑指 Offer 37. 序列化二叉树
二叉树的验证
100. 相同的树
bool isSameTree(TreeNode *p, TreeNode *q) {
// 两个要么都是null ,如果有一个是null 则是不相同的;
if ((p && !q) || (!p && q)) {
return false;
}
if (p == q && !q) {
return true;
}
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
剑指 Offer 28. 对称的二叉树
bool isSymmetric(TreeNode *root) {
return !root ? true : recur(root->left, root->right);
}
bool recur(TreeNode *left, TreeNode *right) {
if (!left && !right) { return true; }
if (!left || !right || left->val != right->val) {
return false;
}
return recur(left->left, right->right) && recur(left->right, right->left);
}
剑指 Offer 55 - II. 平衡二叉树
int depth(TreeNode *root) {
if (!root) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
return max(left, right) + 1;
}
bool isBalanced(TreeNode *root) {
if (!root) {
return true;
}
return abs(depth(root->left) - depth(root->right)) < 2
&& isBalanced(root->left)
&& isBalanced(root->right);
}
98. 验证二叉搜索树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> res;
bool isValidBST(TreeNode *root) {
inOrder(root);
for (int i = 1; i < res.size(); i++) {
if (res[i] <= res[i - 1]) {
return false;
}
}
return true;
}
void inOrder(TreeNode *root) {
if (!root) {
return;
}
inOrder(root->left);
res.push_back(root->val);
inOrder(root->right);
}
};
958. 二叉树的完全性检验
bool isCompleteTree(TreeNode *root) {
queue<TreeNode *> q;
q.push(root);
bool hasNull = false;
while (!q.empty()) {
TreeNode *curr = q.front();
q.pop();
if (curr == nullptr) {
hasNull = true;
continue;
} else {
if (hasNull) {
return false;
}
q.push(curr->left);
q.push(curr->right);
}
}
return true;
}
993. 二叉树的堂兄弟节点
层序遍历时判断父亲节点个数
bool isCousins(TreeNode *root, int x, int y) {
queue<pair<TreeNode *, TreeNode *>> q;
q.push({root, nullptr});
while (!q.empty()) {
int n = q.size();
vector<TreeNode *> cur_parent;
for (int i = 0; i < n; i++) {
auto[cur, parent] = q.front();
q.pop();
if (cur->val == x || cur->val == y) {
cur_parent.push_back(parent);
}
if (cur->left) {
q.push({cur->left, cur});
}
if (cur->right) {
q.push({cur->right, cur});
}
}
if (cur_parent.size() == 0) {
continue;
}
if (cur_parent.size() == 1) {
return false;
}
if (cur_parent.size() == 2) {
return cur_parent[0] != cur_parent[1];
}
}
return false;
}
剑指 Offer 26. 树的子结构
bool isSubStructure(TreeNode *A, TreeNode *B) {
if (!A || !B) {
return false;
}
return (recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
bool recur(TreeNode *A, TreeNode *B) {
if (!B) { return true; }
if (!A || A->val != B->val) {
return false;
}
return recur(A->left, B->left) && recur(A->right, B->right);
}
572. 另一棵树的子树
bool isSubtree(TreeNode *A, TreeNode *B) {
//两棵树 任一一棵都不允许为空
if (!A) {
return false;
}
if (isSameTree(A, B)) {
return true;
}
return isSubtree(A->left, B) || isSubtree(A->right, B);
}
bool isSameTree(TreeNode *q, TreeNode *p) {
if ((!q && p) || (!p && q)) {
return false;
}
if (p == q && !q) {
return true;
}
return q->val == p->val && isSameTree(q->left, p->left) && isSameTree(p->right, q->right);
}
二叉树翻转
剑指 Offer 27. 二叉树的镜像
/**
* 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* mirrorTree(TreeNode* root) {
// write code here
if (root == nullptr) {
return nullptr;
}
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
mirrorTree(root->right);
mirrorTree(root->left);
return root;
}
};
156.上下翻转二叉树
class Solution {
public:
TreeNode *head;
TreeNode upsideDownBinaryTree(TreeNode *root){
if (!root){
return root;
}
dfs(root);
return head;
}
TreeNode *dfs(TreeNode *root){
if (!root){
return false;
}
//对于任意一个节点,它的右节点变成左子结点的左子结点,它自己变成它左子结点的右子节点。
if (!root->left && !root->right){
if (!head){
head = root;
}
return root;
}
TreeNode* left=dfs(root->left);
TreeNode* right=dfs(root->right);
if(!left){
left->left=right;
left->right=root;
}
root->left=nullptr;
root->right=nullptr;
return root;
}
二叉树的深度和直径
剑指 Offer 55 - I. 二叉树的深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){
return 0;
}
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return max(left,right)+1;
}
};
111. 二叉树的最小深度
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
if (!root) { return 0; }
queue<pair<TreeNode *, int>> q;
q.push({root, 1});
while (!q.empty()) {
auto t = q.front();
q.pop();
TreeNode *now = t.first;
int nowDepth = t.second;
if (!now->left && !now->right) {
return nowDepth;
}
if (now->left) {
q.push({now->left, nowDepth + 1});
}
if (now->right) {
q.push({now->right, nowDepth + 1});
}
}
return -1;
}
};
543. 二叉树的直径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxd = 0;
int diameterOfBinaryTree(TreeNode *root) {
depth(root);
return maxd;
}
/**
* 遍历 左右 最深的同时维护一个 maxd
* @param root
* @return
*/
int depth(TreeNode *root) {
if (!root) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
maxd = max(left + right, maxd);
return max(left, right) + 1;
}
};
257. 二叉树的所有路径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<string> res;
string path;
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root,"");
return res;
}
void dfs(TreeNode* root,string path){
if(!root){
return;
}
if(!root->left && !root->right){
path+=to_string(root->val);
res.push_back(path);
return;
}
path+=to_string(root->val)+"->";
dfs(root->left,path);
dfs(root->right,path);
}
};
112. 路径总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return dfs(root,0,targetSum);
}
bool dfs(TreeNode* root,int tmpSum,int targetSum){
if(!root){return false;}
tmpSum+=root->val;
if(!root->left && !root->right){
return tmpSum==targetSum;
}else {
return dfs(root->left,tmpSum,targetSum)
|| dfs(root->right,tmpSum,targetSum);
}
}
};