二叉树

树的知识点

树结构

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

前序遍历

根-左-右。

// 非递归写法
public void preOrder(TreeNode node){
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<TreeNode> s = new Stack<>();//临时栈
        s.push(node);
        while(s.size()>0){
            node = s.pop();
            System.out.println(node.val);//退栈输出结点信息
            if(node.right!=null){
                s.push(node.right);
            }
            if(node.left!=null){
                s.push(node.left);
            }
        }
    }
}
// 递归写法
public void preRecur(TreeNode node){
	if (node == null) return;
	System.out.println(node.val);
	preRecur(node.left);
	preRecur(node.right);
}

中序遍历

左-根-右。

// 非递归写法
public void infixOrder(TreeNode node){
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<TreeNode> s = new Stack<>();//临时栈
        while(s.size()>0 || node != null){
            if(node!=null){
                s.push(node);
                node = node.left;
            }else{
                node = s.pop();
                System.out.println(node.val);//退栈输出结点信息
                node = node.right;
            }
        }		
    }
}
// 递归写法
public void inRecur(TreeNode node){
	if (node == null) return;
	inRecur(node.left);
    System.out.println(node.val);
	inRecur(node.right);
}

后序遍历

左-右-根。使用前序遍历的方法获取 根-右-左 ，然后对结果进行反序。

// 非递归写法
public void postOrder(TreeNode node){
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Stack<TreeNode> s1 = new Stack<>();//临时栈
        Stack<TreeNode> s2 = new Stack<>();//最终结果栈
        s1.push(node);
        while(s1.size()>0){
            node = s1.pop();
            s2.push(node);
            if(node.left!=null){
                s1.push(node.left);
            }
            if(node.right!=null){
                s1.push(node.right);
            }
        }
    }
    while(s2.size()>0){
        System.out.println(s2.pop().val);//退栈输出结点信息
    }
}
// 递归写法
public void postRecur(TreeNode node){
    if (node == null) return;
    postRecur(node.left);
    postRecur(node.right);
    System.out.println(node.val);
}

层次遍历

public void levelOrder(TreeNode node){
    if(node == null){
        System.out.println("二叉树为空");
        return;
    }else{
        Queue<TreeNode> queue = new ArrayList<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            node = queue.poll();
            System.out.println(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }
}