day14 | 二叉树1

0.引言

● 理论基础
● 递归遍历
● 迭代遍历
● 统一迭代

1.二叉树基础

2. 二叉树的前序遍历

Category Difficulty Likes Dislikes
algorithms Easy (71.33%) 1023 -

给你二叉树的根节点 root ，返回它节点值的 前序遍历。

示例 1：

image.png
输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

image.png
输入：root = [1,2]
输出：[1,2]

示例 5：

image.png
输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

Discussion | Solution

2.1.递归法

/*
 * @lc app=leetcode.cn id=144 lang=cpp
 *
 * [144] 二叉树的前序遍历
 */

// @lc code=start
/**
 * 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> preorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    res.push_back(node->val);
    dfs(node->left, res);
    dfs(node->right, res);
  }
};
// @lc code=end

2.2.迭代法

/*
 * @lc app=leetcode.cn id=144 lang=cpp
 *
 * [144] 二叉树的前序遍历
 */

// @lc code=start
/**
 * 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> preorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> node_stack;
    std::vector<int> res;
    if (root == nullptr) return res;
    node_stack.push(root);
    while (!node_stack.empty()) {
      TreeNode* curr_node = node_stack.top();
      node_stack.pop();
      res.push_back(curr_node->val);
      // 右子节点先入栈，等会儿后出栈
      if (curr_node->right) node_stack.push(curr_node->right);
      if (curr_node->left) node_stack.push(curr_node->left);
    }
    return res;
  }
};
// @lc code=end

3. 二叉树的中序遍历

Category Difficulty Likes Dislikes
algorithms Easy (76.23%) 1736 -

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

image.png
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

Discussion | Solution

3.1.递归法

/*
 * @lc app=leetcode.cn id=94 lang=cpp
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * 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> inorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left, res);
    res.push_back(node->val);
    dfs(node->right, res);
  }
};
// @lc code=end

3.2.迭代法

  • 由于访问顺序和处理顺序不一致
  • 1.借用指针遍历访问节点；2.使用栈性质进行处理
/*
 * @lc app=leetcode.cn id=94 lang=cpp
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * 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> inorderTraversal(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> node_stack;
    // 借用指针进行节点访问
    TreeNode* cur = root;

    while (cur != nullptr || !node_stack.empty()) {
      // 深入到“最左”
      if (cur != nullptr) {
        node_stack.push(cur);
        cur = cur->left;
      } else {
        cur = node_stack.top();
        node_stack.pop();
        res.push_back(cur->val); 
        cur = cur->right;
      }
    }
    return res;
  }
};
// @lc code=end

4. 二叉树的后序遍历

Category Difficulty Likes Dislikes
algorithms Easy (76.31%) 1006 -

给你一棵二叉树的根节点 root ，返回其节点值的 **后序遍历 **。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

Discussion | Solution

4.1.递归法

/*
 * @lc app=leetcode.cn id=145 lang=cpp
 *
 * [145] 二叉树的后序遍历
 */

// @lc code=start
/**
 * 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> postorderTraversal(TreeNode* root) {
    std::vector<int> res;
    dfs(root, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, std::vector<int>& res) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left, res);
    dfs(node->right, res);
    res.push_back(node->val);
  }
};
// @lc code=end

4.2.迭代法

/*
 * @lc app=leetcode.cn id=145 lang=cpp
 *
 * [145] 二叉树的后序遍历
 */

// @lc code=start
/**
 * 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> postorderTraversal(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> node_stack;
    if (root == nullptr) return res;
    node_stack.push(root);
    while (!node_stack.empty()) {
      TreeNode* cur = node_stack.top();
      node_stack.pop();
      res.push_back(cur->val);
      // 先入左
      if (cur->left) node_stack.push(cur->left);
      if (cur->right) node_stack.push(cur->right);
    }
    std::reverse(res.begin(), res.end());
    return res;
  }
};
// @lc code=end

5. 二叉树的层序遍历

Category Difficulty Likes Dislikes
algorithms Medium (65.44%) 1612 -

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

image.png
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

Discussion | Solution

5.1.递归法

/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * 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>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    dfs(root, 1, res);
    return res;
  }

 private:
  void dfs(TreeNode* node, int depth, std::vector<std::vector<int>>& res) {
    if (node == nullptr) {
      return;
    }
    if (res.size() < depth) {
      res.push_back(std::vector<int>());
    }
    res[depth - 1].push_back(node->val);
    dfs(node->left, depth + 1, res);   // depth隐式回溯
    dfs(node->right, depth + 1, res);  // depth隐式回溯
  }
};
// @lc code=end

5.2.迭代法

用 queue

/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * 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>> levelOrder(TreeNode* root) {
    if (root == nullptr) return {};

    std::vector<std::vector<int>> res;
    std::queue<TreeNode*> que;
    que.push(root);

    while (!que.empty()) {
      std::vector<int> one_level;
      // int que_size = que,size();
      // for (int i = 0; i < que_size; ++i) {
      // 这里的size是关键，size刚好是每层的节点数
      for (int i = que.size(); i > 0; --i) {
        TreeNode* cur = que.front();
        que.pop();
        one_level.push_back(cur->val);

        if (cur->left) que.push(cur->left);
        if (cur->right) que.push(cur->right);
      }
      res.push_back(one_level);
    }
    return res;
  }
};
// @lc code=end
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容