入队直接入 出队判断当前状态：只有第二栈为空时才从第一栈一次性取得所有数据 class Solution { public: void push(int node) { stack1.push(node); } int pop() { if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } int res = stack2.top(); stack2.pop(); return res; } private: stack<int> stack1; sta...

如果是完全二叉树，第一个空结点出现后，同一层次就不可能出现非空结点 每一层要么出现空结点之后，后面全部是空结点；要么没有出现过空结点 使用队列层次遍历时先左后右进行遍历 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: bool isCompleteTree(TreeNode* root)...

性质：二叉搜索树中序遍历是严格递增序列 做法：遍历时比较当前值和前一个值之间的大小关系即可 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr) { return true; } bo...

能够避免递归尽量避免 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr) { return nullptr; } std::stack<TreeNode *> st...

最近状态及其差 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr || t2 == nullptr) { return t1 == nullptr ? t2 : t1; } TreeNode *head = new TreeNode(t1->val + t2->...

今天毫无状态，唉 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: bool isSymmetrical(TreeNode* pRoot) { if (pRoot == nullptr) { return true; } std::queue<TreeNode *> queue_1, queue_2; queue...

中序遍历：递归 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree == nullptr) { return nullptr; } Convert(pRootOfTree->left); if (pre =...

DFS。。。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == nullptr) { return false; } // 一个结点和对应的路径累加和 std::stack<std::pair<TreeNode *, int>> stack_; stack_.push({roo...

又是层次遍历的运用 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: // 层次遍历，记录最多有多少层 int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } std::queue<TreeNode *> queue_; int count = 0; queue_.push(root); while (!queue_.em...

在层次遍历上的一个简单应用 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: // 这道题观察就可以发现，在层次遍历的基础上 // 奇数层不用翻转，偶数层翻转即可 vector<vector<int> > Print(TreeNode* pRoot) { // 翻转序列的标志 int flag = 1...

一开始确定层数的结点个数卡住了，好好反思！ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: vector<vector<int> > levelOrder(TreeNode* root) { std::queue<TreeNode *> queue_; std::vector<std::vector<int>> res; if (root == n...

递归 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { std::vector<int> res; postorder(root, res); return res; ...

简单递归 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { std::vector<int> res; inorder(root, res); return res; } ...

没啥好讲的，树的遍历只有在迭代中才比较复杂 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { std::vector<int> traverse; preorder_tr...