目录
- 题目描述:94. 二叉树的中序遍历(简单)
- 题目接口
- 解题思路1
- 代码
- 解题思路2
- 代码
- PS:
题目描述:94. 二叉树的中序遍历(简单)
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
LeetCode做题链接:LeetCode-二叉树的中序遍历
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
题目接口
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {}
}
解题思路1
递归实现:
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();dfs(res, root);return res;}private void dfs(List<Integer> res, TreeNode root) {// 递归终止条件if (root == null) {return;}// 左 根 右dfs(res, root.left);res.add(root.val);dfs(res, root.right);}}
解题思路2
迭代实现:
可以用栈来模拟上面的调用过程
- 不断往左子树方向走,每走一次就将当前节点保存到栈中,模拟递归的调用
- 当前节点为空,说明左边走到头了,从栈中弹出节点并保存
- 然后转向右边节点,继续上面整个过程
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<TreeNode>();while(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;}
}
成功!
PS:
感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个赞喔~