二叉树本身固有的递归性质,通常可以用递归算法解决,虽然递归代码简介,但是性能不如非递归算法。
常用的操作是构建二叉树、遍历二叉树(先序、中序、后序、都属于DFS深度优先搜索算法,使用栈来实现),广度优先BFS使用队列来遍历。
参考博客:
注意:
这个图里面虚点框代表的是接口,虚线框代表的是抽象类,实线框代表的实现了接口或者继承了抽象类的类,加粗的实线框代表的是常用类:HashMap、HashSet、ArrayList、LinkedList,这张图没有给出Queue的实现,
可以看到LinkedList是Deque的实现类,所以to sum up,各种栈、队列的接口实现都可以找LinkedList,只是不同的接口都有不同的方法。
下面看leetcode的题目:
【107】Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7}
,
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
] 思路:其实是层序遍历二叉树,编程之美上有这个,其实也就是 BFS,如果使用队列来实现的话,会超时,编程之美上用的vector,所以用一般的动态数组就可以了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/ //It's an iterative way by two "while circles" to travesal every level of the tree, BFS actually, u can use queue to do it ,but it seems time will exceed
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> nodeData = new ArrayList<List<Integer>>();
if(root==null)return nodeData;
List<TreeNode> nodeList = new ArrayList<TreeNode>();
nodeList.add(root);
int start = 0;
int last = 1; //value 1 is for the 0 level
while(start<nodeList.size()){
last = nodeList.size();//update the last value of the new level
List<Integer> tempList = new ArrayList<Integer>(); //store the node data in every level
while(start < last){
TreeNode tempNode = (TreeNode)nodeList.get(start);
if(tempNode!=null)
tempList.add(tempNode.val);
if(tempNode.left!=null)nodeList.add(tempNode.left);
if(tempNode.right!=null)nodeList.add(tempNode.right);
start++;
}
nodeData.add(0,tempList);
} return nodeData; }
}