代码随想录算法训练营Day14| 二叉树递归遍历、 迭代遍历、统一迭代

二叉树递归遍历

代码随想录

思路：

代码：

先序：

class Solution {//递归法
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
 
    private void preorder(TreeNode root, List<Integer> res){//1、确定返回值、参数
        if(root == null){//2、确定终止条件
            return;
        }
        res.add(root.val);//3、先处理（打印）中间节点（先序）
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

中序：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;  
    }
 
    private void inorder(TreeNode root, List<Integer> res){//1、确定返回值、参数
        if(root == null){//2、确定终止条件
            return;
        }
        inorder(root.left, res);
        res.add(root.val);//3、中间处理（打印）中间节点（中序）
        inorder(root.right, res);
    }    
}

后序：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;       
    }
    private void postorder(TreeNode root, List<Integer> res){//1、确定返回值、参数
        if(root == null){//2、确定终止条件
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);//3、最后处理（打印）中间节点（后序）
    }
}

需要注意的点：

迭代遍历

代码随想录

思路：

代码：

先序：

class Solution {//迭代法 中左右
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }        
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        return res; 
    }
}

后序：

class Solution {//迭代法 左右中：中右左顺序颠倒即可
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>(); //进行反转的栈
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode cur = stack1.pop();
            stack2.push(cur);
            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
        }
        while(!stack2.isEmpty()){
            res.add(stack2.pop().val);
        }
        return res;
    }
}

中序：

class Solution {//迭代法 左中右
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }
}

需要注意的点：

1、中序遍历和其他两种遍历不一样，其遍历到的结点不会立刻处理，而是储存到栈里做记录。

2、注意前序、后续遍历左右结点的入栈顺序。

统一迭代

代码随想录

思路：

从头结点开始考虑，按照遍历的相反顺序压入栈，并在中点后加入null作为开始处理此结点的标记。

代码：

中序：

class Solution {//迭代法：统一写法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.peek();//读取栈顶元素（结点）
            if(cur != null){//没有遇到需要处理的节点
                stack.pop();
                if(cur.right != null){
                    stack.push(cur.right);
                }
                stack.push(cur);
                stack.push(null);//标记一下还没处理
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }else{//碰到null标记就开始录入结果
                stack.pop();//将null删除
                res.add(stack.pop().val);//录入并删除
            }
        }
        return res;
    }
}

 其余两种遍历同理

需要注意的点：