建设项目自主验收验收网站,象山网站建设,网站模板中文,济南网站建设在哪里【LetMeFly】94.二叉树的中序遍历#xff1a;递归/迭代(栈模拟递归)
力扣题目链接#xff1a;https://leetcode.cn/problems/binary-tree-inorder-traversal/
给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。 示例 1#xff1a; 输入#xff1a;root […【LetMeFly】94.二叉树的中序遍历递归/迭代(栈模拟递归)
力扣题目链接https://leetcode.cn/problems/binary-tree-inorder-traversal/
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 示例 1 输入root [1,null,2,3]
输出[1,3,2]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100 进阶: 递归算法很简单你可以通过迭代算法完成吗
方法一深度优先搜索DFS(递归)
写一个函数进行深搜
函数接受一个节点作为参数若节点为空则直接返回否则递归左子节点当前节点加入答案递归右子节点。
从根节点开始使用上述函数递归递归完成后返回答案。
时间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))空间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))
AC代码
C
class Solution {
private:vectorint ans;void dfs(TreeNode* root) {if (!root) {return ;}dfs(root-left);ans.push_back(root-val);dfs(root-right);}
public:vectorint inorderTraversal(TreeNode* root) {dfs(root);return ans;}
};Python
# from typing import Optional, List# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def dfs(self, root: Optional[TreeNode]) - None:if not root:returnself.dfs(root.left)self.ans.append(root.val)self.dfs(root.right)def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:self.ans []self.dfs(root)return self.ans方法二使用栈模拟递归栈模拟递归
递归过程中实际上是系统使用栈帮你存下了当前的信息调用函数结束后恢复当前信息继续往下执行。因此我们使用栈模拟一下递归即可。
递归的时候都需要保存哪些信息呢其实我们只需要保存当前节点是什么和当前节点是否递归过(左)子节点即可。
若是第一次处理到这个节点则先将右子入栈再将本节点再次入栈并标记一下说左子节点入过栈了最后将左子节点入栈。这样出栈顺序将时左中右
出栈时先看节点是否为空为空直接返回。若左子节点入栈过了则将当前节点值加入答案否则左子还未入栈执行“第一次处理到这个节点”的操作。
时间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))空间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))
使用栈模拟递归时空复杂度都不变但毕竟保存的信息变少了将会更高效。
AC代码
C
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ans;stackpairTreeNode*, bool st; // [node, ifPushedChild, ...st.push({root, false});while (st.size()) {auto [thisNode, ifPushedChild] st.top();st.pop();if (!thisNode) {continue;}if (ifPushedChild) {ans.push_back(thisNode-val);}else {st.push({thisNode-right, false});st.push({thisNode, true});st.push({thisNode-left, false});}}return ans;}
};Python
# from typing import Optional, List# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:ans []st [(root, False)]while st:thisNode, ifPushedChild st.pop()if not thisNode:continueif ifPushedChild:ans.append(thisNode.val)else:st.append((thisNode.right, False))st.append((thisNode, True))st.append((thisNode.left, False))return ans 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136090242
