算法学习day14-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法学习day14。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

144. 二叉树前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

思路(递归)

根左右，空返回
时间 O(n)
空间 O(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 {
    List<Integer> ret = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return ret ;
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret ;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

迭代

递归的本质即是“栈”
前序≈根左右，要想实现左节点先出，则需要先将右节点压入栈，入栈根-右-左，出栈：根左右

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

        return res ;
    }
}

94. 二叉树中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

思考（递归）

左根右，空返回

复杂度

时间O(n)
空间O(1)


import java.util.ArrayList;

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

迭代

循环条件：当前节点不为null或者栈非空
左根右，需要先遍历左子树，遍历完后，从队列弹出，遍历右子树
入栈顺序，左子树先全部入栈，在出栈是获取值，然后迭代右子树

class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        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;
    }
}

145.二叉树后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。文章来源地址https://www.toymoban.com/news/detail-474118.html

输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

思考（递归）

左右根，空返回

复杂度

时间 O(nlongn)
空间 O(n)

class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return ret;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        ret.add(root.val);

        return ret ;

    }
}

迭代

和前序遍历相反，前序遍历的入栈顺序：根-左-右，出栈：根右左
后续的出栈应该为：左右根，将结果翻转即可

class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()) {
            root = stack.pop();
            res.add(root.val);
            if(root.left!= null)  stack.push(root.left);
            if(root.right!= null) stack.push(root.right);

        }
        Collections.reverse(res);
        return res;
    }
}