LeetCode 94. Binary Tree Inorder Traversal
程序员文章站
2022-05-20 13:50:01
...
问题描述
- Given a binary tree, return the inorder traversal of its nodes’ values.
- Follow up: Recursive solution is trivial, could you do it iteratively?
- 地址
问题分析
- 实现二叉树中序遍历的方法
- 递归
- 非递归
- 教科书法(压左边界)
- 金手指法
代码实现
- 递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorderTraversal(root, res);
return res;
}
public void inorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorderTraversal(root.left, res);
res.add(root.val);
inorderTraversal(root.right, res);
}
- 非递归:教科书法
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curNode = root;
while (curNode != null || ! stack.isEmpty()) {
while (curNode != null) {
//第一次遇到该节点(前序)
stack.push(curNode);
curNode = curNode.left;
}
//第二次遇到该节点(中序)
curNode = stack.pop();
res.add(curNode.val);
curNode = curNode.right;
}
return res;
}
- 非递归金手指法
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> res = new ArrayList<>();
Stack<Command> stack = new Stack<>();
//初始化
stack.push(new Command(false, root));
while(! stack.isEmpty()) {
Command curCommand = stack.pop();
TreeNode curRoot = curCommand.root;
if (curCommand.isPrint) {
res.add(curRoot.val);
}else {
//此时指令入栈顺序是右(遍历)根(打印)左(遍历)
//出栈后便是左(遍历)根(打印)右(遍历),便实习了中序遍历
if (curRoot.right != null) {
stack.push(new Command(false, curRoot.right));
}
stack.push(new Command(true, curRoot));
if (curRoot.left != null) {
stack.push(new Command(false, curRoot.left));
}
}
}
return res;
}
//用于指示该root是打印还是遍历
class Command{
boolean isPrint;
TreeNode root;
public Command(boolean isPrint, TreeNode root) {
this.isPrint = isPrint;
this.root = root;
}
}
推荐阅读
-
leetcode笔记:Invert Binary Tree
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
Leetcode——108. Convert Sorted Array to Binary Search Tree
-
Leetcode 108. Convert Sorted Array to Binary Search Tree
-
LeetCode 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )
-
LeetCode 235--二叉搜索树的最近公共祖先 ( Lowest Common Ancestor of a Binary Search Tree ) ( C语言版 )
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树
-
[Leetcode] 235. Lowest Common Ancestor of a Binary Search Tree
-
leetcode 235. Lowest Common Ancestor of a Binary Search Tree(二叉树的最低共同祖先)
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree