leetcode — binary-tree-inorder-traversal
2024-04-25 00:10:53
import java.util.Arrays;
import java.util.Stack;
import java.util.TreeMap;
/**
*
* Source : https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
*
*
* 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.
*
* OJ's Binary Tree Serialization:
*
* The serialization of a binary tree follows a level order traversal, where '#' signifies
* a path terminator where no node exists below.
*
* Here's an example:
*
* 1
* / \
* 2 3
* /
* 4
* \
* 5
*
* The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
*
*/
public class BinaryTreeInOrderTraversal {
private int[] result = null;
int pos = 0;
public int[] traversal(char[] tree) {
result = new int[tree.length];
pos = 0;
traversalByRecursion(createTree(tree));
return result;
}
public int[] traversal1(char[] tree) {
result = new int[tree.length];
pos = 0;
traversalbyIterator(createTree(tree));
return result;
}
/**
* 对二叉树进行中序遍历
*
* 树的遍历分为：
* 深度优先：
* 先序遍历：先访问根节点然后依次访问左右子的节点
* 中序遍历：先访问左子节点，然后访问根节点，在访问右子节点
* 后序遍历：先访问左右子节点，然后访问根节点
*
* 先用递归实现中序遍历
*
* @param root
* @return
*/
public void traversalByRecursion(TreeNode root) {
if (root == null) {
return;
}
traversalByRecursion(root.leftChild);
result[pos++] = root.value;
traversalByRecursion(root.rightChild);
}
/**
* 使用循环来进行中序遍历,借助栈实现
*
* @param root
*/
public void traversalbyIterator (TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while (cur != null || stack.size() > 0) {
if (cur == null) {
// 当前节点为空，表示已经是叶子节点，
TreeNode node = stack.pop();
result[pos++] = node.value;
cur = node.rightChild;
} else {
stack.push(cur);
cur = cur.leftChild;
}
}
}
public TreeNode createTree (char[] treeArr) {
TreeNode[] tree = new TreeNode[treeArr.length];
for (int i = 0; i < treeArr.length; i++) {
if (treeArr[i] == '#') {
tree[i] = null;
continue;
}
tree[i] = new TreeNode(treeArr[i]-'0');
}
int pos = 0;
for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
if (tree[i] != null) {
tree[i].leftChild = tree[++pos];
if (pos < treeArr.length-1) {
tree[i].rightChild = tree[++pos];
}
}
}
return tree[0];
}
private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value;
public TreeNode(int value) {
this.value = value;
}
public TreeNode() {
}
}
public static void main(String[] args) {
BinaryTreeInOrderTraversal binaryTreeInOrderTraversal = new BinaryTreeInOrderTraversal();
char[] arr1 = new char[]{'1','#','2','3'};
char[] arr2 = new char[]{'1','2','3','#','#','4','#','#','5'};
System.out.println(Arrays.toString(binaryTreeInOrderTraversal.traversal(arr1)));
System.out.println(Arrays.toString(binaryTreeInOrderTraversal.traversal(arr2)));
System.out.println(Arrays.toString(binaryTreeInOrderTraversal.traversal1(arr1)));
System.out.println(Arrays.toString(binaryTreeInOrderTraversal.traversal1(arr2)));
}
}
最新文章
- CSS制作三角形和按钮
- [LeetCode] Sliding Window Maximum 滑动窗口最大值
- wechall.net/stegano 解题心得
- 树莓派+移动硬盘搭建NAS服务器
- chkconfig命令详解
- java分享第二天（变量及命名规范）
- [置顶] ios 网页中图片点击放大效果demo
- 第三百天了 how can I 坚持
- Java NIO和IO的主要区别
- 在Xcode中如何屏蔽某个源文件的编译警告信息
- 关于找工作（二 Cover Letter）
- Kafka集群在空载情况下Cpu消耗比较高的问题
- 【stanford C++】字符串(String)与流(Stream)
- Fragment管理
- Javascript编码规范，好的代码从书写规范开始，增强代码的可读性，可维护性，这是相当重要的！
- 航遇项目react踩坑
- python集合操作
- mysql解决数据库死锁问题
- Django的学习（一）————初入django
- spring util list