二叉树(LeetCode) C++相关知识代码 系列1

0、二叉树最大深度

原题目:Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

方法:求最大深度的时候,只需要比较左右子树的深度,取较大者+1就行了

C++代码:

class Solution

{
public: int minDepth(TreeNode *root){ if(root==Null) return ;
int l=minDepth(root->left);
int r=minDepth(root->right);
if(l==||r==)
return +l+r;
return +min(l,r);
} };

1、二叉树最小深度

原题目:Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

方法:求最小深度的时候,需要区分双子树与单子树,双子树时,深度较小者+1,单子树时(即左右子树有一颗为空时)为深度较大者+1

C++代码:

class Solution{

public:
int maxDepth(TreeNode *root){ if (root==NULL)
{
return ;
}
int l=maxDepth(root->left);
int r=maxDepth(root->right);
return +max(l,r); } };

2、Given a binary tree, return the postorder traversal of its nodes' values.

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

   1
\
2
/
3

  return[3,2,1].

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

方法:后序遍历,使用vector栈来做,先将父节点入栈,再将右孩子入栈,左孩子入栈。那么返回时就能可以倒序输出后序遍历值。

class Solution{
public:
void postOrder(TreeNode *root,vector<int>&vec){
if (root!=NULL)
{
postOrder(root->left,vec);
postOrder(root->right,vec);
vec.push_back(root->val);
}
}
vector<int>postorderTraversal(TreeNode *root){
vector<int> vec;
postOrder(root,vec);
return vec;
} };
上一篇:Unity场景间数据传递方法


下一篇:vue 组件间数据传递