首页 > 其他分享 >LeetCode_0144. 二叉树前序遍历 & LeetCode_0096. 二叉树中序遍历 & LeetCode_0145. 二叉树后序遍历

LeetCode_0144. 二叉树前序遍历 & LeetCode_0096. 二叉树中序遍历 & LeetCode_0145. 二叉树后序遍历

时间:2024-09-15 17:38:38浏览次数:7  
标签:遍历 return current vector 二叉树 ans myStack root LeetCode

题目描述

  给你二叉树的根节点 root ,返回它节点值的 前序 / 中序 / 后序 遍历。

递归写法

LeetCode_0144. 前序

中左右

  void myPreorder(TreeNode* root, vector<int>& ans) {
      if(!root) {
          return;
      }

      ans.emplace_back(root->val);
      myPreorder(root->left, ans);
      myPreorder(root->right, ans);

      return;
  }
  vector<int> preorderTraversal(TreeNode* root) {
      vector<int> ans;
      myPreorder(root, ans);
      return ans;
  }

LeetCode_0094. 中序

左中右

  void myInorder(TreeNode* root, vector<int>& ans) {
        if(!root) {
          return;
      }

      myInorder(root->left, ans);
      ans.emplace_back(root->val);
      myInorder(root->right, ans);

      return;
  }
  vector<int> inorderTraversal(TreeNode* root) {
      vector<int> ans;
      
      myInorder(root, ans);

      return ans;
  }

LeetCode_0145. 后序

左右中

  void myPostorder(TreeNode* root, vector<int>& ans) {
      if(!root) {
          return;
      }

      myPostorder(root->left, ans);
      myPostorder(root->right, ans);
      ans.emplace_back(root->val);

      return;
  }
  vector<int> postorderTraversal(TreeNode* root) {
      vector<int> ans;
      
      myPostorder(root, ans);

      return ans;
  }

迭代写法

栈内是待访问的结点,current是当前搜索到的结点。

LeetCode_0144. 前序

从root开始,先访问current,right入栈,转向left搜索。

  vector<int> preorderTraversal(TreeNode* root) {
      vector<int> ans;
      stack<TreeNode*> myStack;
      // 搜索从root开始
      TreeNode *current = root;

      // 当前搜索到叶子且没有待搜索结点时,结束搜索
      while(current || !myStack.empty()) {
          // 当前结点
          if(current) {
              // 中
              ans.emplace_back(current->val);
              // 右孩子待搜索
              myStack.emplace(current->right);
              // 搜索左孩子
              current = current->left;
          // 当前结点走到头了,就取出一个待搜索结点
          } else {
              current = myStack.top();
              myStack.pop();
          }
      }

      return ans;
  }

LeetCode_0094. 中序

从root开始,current先入栈,转向left。
每当current搜索到头了,回退一步访问栈顶元素,转向栈顶元素的right。(一路向左,回退访问,向右)

  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> myStack;
    TreeNode* current = root;

    while(current || !myStack.empty()) {
        if(current) {
            myStack.emplace(current);
            current = current->left;
        } else {
            current = myStack.top();
            myStack.pop();
            ans.emplace_back(current->val);
            current = current->right;
        }
    }

    return ans;
  }

LeetCode_0145. 后序

解法跟前序非常相似。
后续遍历是左右中,反过来 就是 中右左,跟前序一样,也是先访问自己再访问孩子。
因此只需要解出 中右左 ,再reverse()就可以了。

从root开始搜索,left先入栈,转向搜索right。

  vector<int> postorderTraversal(TreeNode* root) {
      vector<int> ans;
      stack<TreeNode*> myStack;
      TreeNode *current = root;

      while(current || !myStack.empty()) {
          if(current) {
              ans.emplace_back(current->val);
              myStack.emplace(current->left);
              current = current->right;
          } else {
              current = myStack.top();
              myStack.pop();
          }
      }

      reverse(ans.begin(), ans.end());

      return ans;
  }

标签:遍历,return,current,vector,二叉树,ans,myStack,root,LeetCode
From: https://www.cnblogs.com/GaogaoBlog/p/18415447

相关文章

  • 二叉树的所有路径(所有从根节点到叶子节点的路径)-257
    题目描述给你一个二叉树的根节点root,按任意顺序,返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。解题思路这道题我们采用二叉树里的前序遍历方式,我们要遍历所有到叶子节点的路径,我们采用复用的思想,就是让这里的几个数据结构我们可以重复使用,但是重复使......
  • 496. 下一个更大元素 I(leetcode)
    https://leetcode.cn/problems/next-greater-element-i/description/根据校验nums2中的元素是否存在于nums1中的时机分为不同做法classSolution{publicint[]nextGreaterElement(int[]nums1,int[]nums2){Deque<Integer>st=newArrayDeque<>();......
  • 739. 每日温度(leetcode)
    https://leetcode.cn/problems/daily-temperatures/description/经典单调栈,关键难点在于如何利用单调栈这个数据结构解题题意要求向右找到第一个比当前大的元素,若是暴力则是O(n^2),但是依据暴力的这个思想可以利用单调栈优化,因为求右边第一个比当前元素大的元素,等价于求当前......
  • C++: 二叉树进阶面试题
    做每件事之前都心存诚意,就会事半功倍.目录前言1.根据二叉树创建字符串2.二叉树的层序遍历Ⅰ3.二叉树的层序遍历Ⅱ4.二叉树的最近公共祖先5.二叉搜索树与双向链表6.根据一棵树的前序遍历与中序遍历构造二叉树7.根据一棵树的中序遍历与后序遍历构造二叉树8.二......
  • 二叉树的 Morris 中序遍历
    回顾问题陈述:给定一棵二叉树,实现中序遍历并返回包含其中序序列的数组例如给定下列二叉树:我们按照左、根、右的顺序递归遍历二叉树,得到以下遍历:最终中序遍历结果可以输出为:[3,1,9,2,4,7,5,8,6]MorristrickMorris中序遍历是一种树遍历算法,旨在实现O(1)的空间......
  • LeetCode 2848. 与车相交的点(差分法、前缀和)
    题目:2848.与车相交的点思路:差分+前缀和。先找到数组中的最大值N,然后构建一个长度为N+2的数组sta。接着遍历数组,进行差分。最后求前缀和得到每个点的值,然后判断是否大于0即可。时间复杂度0(n)。classSolution{public:intnumberOfPoints(vector<vector<int>>&nu......
  • 【数据结构和算法实践-树-LeetCode113-路径总和Ⅱ】
    数据结构和算法实践-树-LeetCode113-路径总和Ⅱ题目MyThought代码示例JAVA-8题目给你二叉树的根节点root和一个整数目标和targetSum,找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点输入:root=[5,4,8,11,null,13......
  • LeetCode_0044. 通配符匹配,带字母'*''?'的模式串匹配仅带字母的主串
    题目描述  给你一个输入字符串(s)和一个字符模式(p),请你实现一个支持'?'和'*'匹配规则的通配符匹配:  1.'?'可以匹配任何单个字符。  2.'*'可以匹配任意字符序列(包括空字符序列)。  3.判定匹配成功的充要条件是:字符模式必须能够完全匹配输入字符串(而不是......
  • Leetcode面试经典150题-739.每日温度
    应读者私信要求,本题协商题目的具体内容给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。示例1:输入:temperatures=[73,74,......
  • 【二叉树的最大深度】带你理解递归奥妙!
    ......