自己做炉石卡牌的网站,网络广告策划书模板,wordpress商业化插件,wordpress静用字体Hot100 - 二叉树的中序遍历 最佳思路#xff1a;
中序遍历的顺序是#xff1a;左子树 - 根节点 - 右子树。为了实现这个顺序#xff0c;我们可以利用栈来模拟递归过程#xff0c;从而避免栈溢出的问题。在遍历过程中#xff0c;始终向左子树深入#xff0c;直到…Hot100 - 二叉树的中序遍历 最佳思路
中序遍历的顺序是左子树 - 根节点 - 右子树。为了实现这个顺序我们可以利用栈来模拟递归过程从而避免栈溢出的问题。在遍历过程中始终向左子树深入直到叶子节点为止然后回溯并访问节点再转向右子树。
时间复杂度
时间复杂度为 O(n)其中 n 为二叉树的节点数。每个节点都被访问一次因此时间复杂度为线性。空间复杂度为 O(h)其中 h 是二叉树的高度。最坏情况下栈的空间复杂度为树的高度即树为完全不平衡时为 O(n)最优情况下为平衡二叉树时为 O(log n)。
思路解析
使用栈模拟递归在中序遍历中首先访问左子树再访问根节点最后访问右子树。传统的递归方式非常直观但栈的实现可以有效避免递归深度过大导致栈溢出的风险。模拟遍历过程我们从根节点开始反复将当前节点及其左子树压入栈中。直到左子树为空即叶子节点然后开始弹出栈中的节点并访问它们接着访问其右子树。这样可以确保中序遍历的顺序。边界条件处理需要在栈为空并且当前节点为空时停止遍历确保程序不会无限循环。
代码实现
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();// 继续遍历直到栈为空且节点为 nullwhile (stack.size() 0 || root ! null) {// 深入左子树if (root ! null) {stack.add(root);root root.left; // 遍历到左子树的最深节点} else {// 弹出栈顶元素访问节点TreeNode tmp stack.pop();res.add(tmp.val);// 转向右子树root tmp.right;}}return res;}
}思路总结
本题的关键在于如何通过栈模拟递归来实现中序遍历。通过控制栈的操作我们能够按顺序遍历每一个节点避免递归的深度问题。相较于传统递归迭代的栈方式在某些场景下能更好地控制空间复杂度尤其是在树结构较大时。
