leetCode 94.Binary Tree Inorder Traversal(二叉树中序遍历) 解题思路和方法
2023-09-11 14:14:09 时间
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [1,3,2]
.
Note: Recursive solution is trivial, could you do it iteratively?
confused what "{1,#,2,3}"
means?
> read more on how binary tree is serialized on OJ.
思路:二叉树的中序遍历,是典型的递归算法。可是题目中建议非递归实现。所以还是有些思考的。
只是算是基础题。感觉是必须掌握的。
代码例如以下(递归实现):
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { List<Integer> list = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { /** * 中序遍历,先左子树,再根,最后右子树 */ if(root == null) return list; if(root.left != null){ inorderTraversal(root.left); } list.add(root.val); if(root.right != null){ inorderTraversal(root.right); } return list; } }非递归实现:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { /** * 非递归实现中序遍历 * 中序遍历,先左子树,再根。最后右子树 */ List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; TreeNode p = root; Stack<TreeNode> st = new Stack<>(); while(p != null || !st.isEmpty()){ if(p != null){ st.push(p); p = p.left; }else{ p = st.pop(); list.add(p.val); p = p.right; } } return list; } }
相关文章
- Java实现 LeetCode 823 带因子的二叉树(DP)
- Java实现 LeetCode 731 我的日程安排表 II(二叉树)
- Java实现 LeetCode 729 我的日程安排表 I(二叉树)
- Java实现 LeetCode 655 输出二叉树(DFS+二分)
- Java实现 LeetCode 637 二叉树的层平均值(遍历树)
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- Java实现 LeetCode 104 二叉树的最大深度
- LeetCode(107): 二叉树的层次遍历 II
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- LeetCode: 102_Binary Tree Level Order Traversal | 二叉树自顶向下的层次遍历 | Easy
- LeetCode:144_Binary Tree Preorder Traversal | 二叉树的前序遍历 | Medium
- LeetCode:145_Binary Tree Postorder Traversal | 二叉树后序遍历 | Hard
- LeetCode(124):二叉树中的最大路径和
- ( “树” 之 DFS) 617. 合并二叉树 ——【Leetcode每日一题】
- leetcode 236. 二叉树的最近公共祖先
- 【LeetCode-面试算法经典-Java实现】【144-Binary Tree Preorder Traversal(二叉树非递归前序遍历)】
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【LeetCode】124.二叉树中的最大路径和