二叉树的深度遍历

用于个人记录

1)前序遍历

递归:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }
    public void preorder(TreeNode root , List<Integer> list){
        if(root == null) return;
        
        //处理单层逻辑
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
        
    }
}

迭代:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null)return ans;
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        
        while(!stack.isEmpty()){
            TreeNode temp = stack.removeLast();
            ans.add(temp.val);
            if (temp.right!=null)stack.addLast(temp.right);
            if (temp.left!=null)stack.addLast(temp.left);
        }
        return ans;
    }
  
}

2)后序遍历

递归:

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        backorder(root, ans);
        return ans;
    }
    public void backorder(TreeNode root, List<Integer> list){
        if(root == null ) return ;
        //
        backorder(root.left, list);
        backorder(root.right, list);
        list.add(root.val);
    }
}

迭代:

可以由前序遍历稍微改点代码而来: 前序(中左右)---->改变前序遍历中某个节点的左右节点加入栈的顺序(即变为中右左)--->反转最终list中的顺序(即变为左右中)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null)return ans;
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        
        while(!stack.isEmpty()){
            TreeNode temp = stack.removeLast();
            ans.add(temp.val);
            if (temp.left!=null)stack.addLast(temp.left);
            if (temp.right!=null)stack.addLast(temp.right);
            
        }
        
        Collections.reverse(ans);
        return ans;
    }
   
}

3)中序遍历

递归：

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>  ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
        
    }
    public void inorder(TreeNode root, List<Integer> list){
        if(root == null) return;
        //
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

迭代：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>  ans = new ArrayList<>();
        if(root == null) return ans;
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root!=null){
            while(root!=null){
                stack.addLast(root);
                root = root.left;
            }
            root = stack.removeLast();
            ans.add(root.val);
            
             root = root.right;
            
        }
        return ans;
        
    }
   
}