二叉树结点结构

1
2
3
4
5
6
7
8
9
10
11
12
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
    @Override
    public String toString(){
        return "val: "+val;
    }
}

访问函数

1
2
3
public void visit(TreeNode node){
    System.out.print(node.val+" ");
}

前序遍历

递归实现

1
2
3
4
5
6
public void preOrderRecursion(TreeNode node){
    if(node==null)return;
    visit(node);
    preOrderRecursion(node.left);
    preOrderRecursion(node.right);
}

非递归实现

使用栈:根节点出栈，右节点入栈，左节点入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> preStack=new Stack<TreeNode>();
        if(root==null)return result;
        preStack.push(root);
        while(!preStack.isEmpty()){
            TreeNode nodeNow=preStack.pop();
            result.add(nodeNow.val);
            if(nodeNow.right!=null)preStack.push(nodeNow.right);
            if(nodeNow.left!=null)preStack.push(nodeNow.left);
        }
        return result;
    }
}

中序遍历

非递归实现

使用栈+双层循环：内层循环不停寻找左孩子并入栈，直到没有左孩子；外层循环每次pop出栈顶元素，并都把右孩子（如果有）入栈。

注意一点：外层循环的判断条件是或，即只要栈非空或者结点有右孩子，就继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> inStack=new Stack<TreeNode>();
        TreeNode currentNode=root;
        while(!inStack.isEmpty()||currentNode!=null){      
            while(currentNode!=null){
                inStack.push(currentNode);
                currentNode=currentNode.left;
            }
            currentNode=inStack.pop();
            result.add(currentNode.val);
            currentNode=currentNode.right;
        }
        return result;
    }
}

后序遍历

非递归实现

使用一个栈和一个hashmap，hashmap记录节点是否被访问过。

四种情况访问这个节点：

  • 没有左右孩子

  • 只有左孩子且左孩子已被访问

  • 只有右孩子且右孩子已被访问

  • 有左右孩子且左右孩子都被访问

左孩子未被访问，则不断把左孩子入栈

右孩子未被访问，把这个右孩子入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        Stack<TreeNode> postStack=new Stack<TreeNode>();
        Map<TreeNode,Integer> visitedNode=new HashMap<TreeNode,Integer>();
        if(root==null)return result;
        postStack.push(root);
        while(!postStack.isEmpty()){
            TreeNode currentNode=postStack.peek();
            if( (currentNode.left==null&&currentNode.right==null)||
                (currentNode.left==null&&currentNode.right!=null&&visitedNode.containsKey(currentNode.right))||
                (currentNode.right==null&&currentNode.left!=null&&visitedNode.containsKey(currentNode.left))||
                (currentNode.right!=null&&currentNode.left!=null&&visitedNode.containsKey(currentNode.left)&&visitedNode.containsKey(currentNode.right))){
                result.add(currentNode.val);
                visitedNode.put(currentNode,1);
                postStack.pop();
                continue;
            }
            if(currentNode.left!=null&&(!visitedNode.containsKey(currentNode.left))){
                while(currentNode.left!=null){
                    postStack.push(currentNode.left);
                    currentNode=currentNode.left;
                }
            }
            if(currentNode.right!=null&&(!visitedNode.containsKey(currentNode.right))){
                postStack.push(currentNode.right);
            }
        }
        return result;
    }
}

层序遍历

非递归实现

  • 使用队列，每次结点出栈后将左右结点依次入队
  • 使用变量levelNum保存当前层的结点个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        Queue<TreeNode> nodeQueue=new LinkedList<TreeNode>();
        if(root==null)return result;
        nodeQueue.offer(root);
        int levelNum=1;
        while(!nodeQueue.isEmpty()){
            List<Integer> levelList=new ArrayList<>();
            while(levelNum!=0){
                TreeNode tmp=nodeQueue.poll();
                if(tmp.left!=null){
                    nodeQueue.offer(tmp.left);
                }
                if(tmp.right!=null){
                    nodeQueue.offer(tmp.right);
                }
                levelList.add(tmp.val);
                levelNum--;
            }
            result.add(levelList);
            levelNum=nodeQueue.size();
        }
        return result;
    }
}