昨晚中兴笔试题，第一题是给定二叉树，每个节点的数据结构是 value,left,right，比较根节点到各个叶子节点路径和的大小，输出路径和的最小值。(补充：用ArrayList可以存储)
以前没做过关于树的题，所以没想到如何处理各个节点的左右子节点，即不会遍历二叉树，在这里做一个总结
1.递归实现遍历
//递归实现遍历，各种不同的遍历实际上是输出的位置不同，但是都是递归
//先序遍历，传入 t = root1
public void preOrder(Node t){
if(t == null)
return;
System.out.println(t.getValue());
pre(t.getLeft());
pre(t.getRight());
}
//中序遍历，传入 t = root1
public void inOder(Node t){
if(t == null)
return;
inOrder(t.getLeft());
System.out.println(t.getValue());
inOrder(t.getRight());
}
//后序遍历，传入 t = root1
public void postOder(Node t){
if(t == null)
return;
postOrder(t.getLeft());
postOrder(t.getRight());
System.out.println(t.getValue());
2.非递归实现遍历
非递归实现遍历，用到栈来存储路径，输出路径
//先序遍历1，传入t =root1
public void iteratorPre(Node t){
Stack<Node> stack = new Stack<Node>();
stack.push(t);
//每次取出节点的顺序总是根，左，右
while(!stack.Empty()){
t = stack.pop();
System.out.println(t.getValue());
//先压入右节点，再压入左节点，因为栈是先进后出的
if(t.getRight() != null)
stack.push(t.getRight());
if(t.getLeft() != null)
stack.push(t.getLeft());
}
}
//先序遍历2
protected static void iterativePreorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点，压入前访问它
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {//
node = stack.pop();
node = node.getRight();
}
}
}
//中序遍历，传入 t = root1
protected static void iterativeInorder(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
//压入根节点和左节点
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node);
node = node.getRight();
}
}
}
//后序遍历，单栈
protected static void iterativePostorder3(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
3.计算所有路径中的最小值
import java.util.;
public class Main{
/来源：
* 中兴机试题：计算二叉树根节点到叶子节点的最短路径
* 注意：为了记录路径，用栈，找到叶子节点后计算，然后pop()出去，再找下一个
* */
static List<Integer> list = new ArrayList<Integer>();
public static void main(String[] args){
Node root1 = new Node();
Node node1 = new Node();
Node node2 = new Node();
Node node3 = new Node();
Node node4 = new Node();
Node node5 = new Node();
Node node6 = new Node();
root1.setLeft(node1);
root1.setRight(node2);
node1.setLeft(node3);
node1.setRight(node4);
node4.setLeft(node5);
node4.setRight(node6);
root1.setValue(8);
node1.setValue(8);
node2.setValue(7);
node3.setValue(9);
node4.setValue(2);
node5.setValue(4);
node6.setValue(7);
//先序遍历
//pre(root1);
//用栈记录路径
Stack<Node> n = new Stack<Node>();
findMin(root1,n);
//list中是各条路径的和
for(int i = 0;i < list.size();i++){
System.out.println(list.get(i));
}
}
//递归实现，每当发现叶子节点，就计算一次
public static void findMin(Node t,Stack<Node> n){
if(t == null)
return;
n.push(t);
//t是叶子节点,此时计算路径和
if(t.getLeft() == null && t.getRight() == null){
int sum =0;
//clone()方法，避免修改原来的栈
Stack<Node> s1= (Stack<Node>)n.clone();
for(int j =0;j < n.size();j++){
sum += s1.pop().getValue();
}
list.add(sum);
//去除叶子节点
n.pop();
}else{
//递归寻找
findMin(t.getLeft(),n);
findMin(t.getRight(),n);
//经过该节点的路径已找完，删除该节点
n.pop();
}
}
public static void pre(Node t){
if(t == null)
return;
System.out.println(t.getValue());
pre(t.getLeft());
pre(t.getRight());
}
}
//节点结构
class Node{
private int value;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
private Node left;
private Node right;
}
网友评论