day14-二叉树part01(递归法/迭代法)

    递归三部曲(时刻牢记)

        1.确认递归函数需要的参数与返回值

            一般为传入一个根节点 传入一个数组用来存放结果数组

        2.确定终止条件

        3.确定单层递归逻辑

递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。

迭代用栈完成

二叉树的定义

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;
    }
}

144. 二叉树的前序遍历 (根左右)

          递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root,result);
        return result;
    }

    public void preorder(TreeNode root,List<Integer> result){
        if(root == null){
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }
}

          迭代(    迭代用栈  前序遍历 中左右  进栈顺序 中右左)

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

145. 二叉树的后序遍历 (左右根)

        递归

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root,result);
        return result;
    }
    private void postorder(TreeNode root,List<Integer> result){
        if(root == null){
            return;
        }
        postorder(root.left,result);
        postorder(root.right,result);
        result.add(root.val);
    }
}

        迭代

    前序遍历根左右    总是先出根结果 进栈顺序 根 右 左  出栈  根 左 右

    后序遍历左右根                              进栈顺序 根 左 右  出栈 根 右 左  再反转结果集 左右根

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

94. 二叉树的中序遍历 (左根右)

        递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root,result);
        return result;
    }

    public void inorder(TreeNode root,List<Integer> result){
        if(root == null){
            return;
        }
        inorder(root.left,result);
        result.add(root.val);
        inorder(root.right,result);
    }
}

        迭代(    中序遍历 左 根 右  一直遍历到最左子节点 弹出 每次弹出先添加右节点)

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

相关推荐

  1. day14-part01(/)

    2024-04-01 15:18:01       7 阅读

最近更新

  1. 原版Win7 本地离线安装.netframework 4.8

    2024-04-01 15:18:01       0 阅读
  2. MyEclipse tomcat debug 断点看不到变量值

    2024-04-01 15:18:01       0 阅读
  3. MAC 终端命令

    2024-04-01 15:18:01       0 阅读
  4. 2024年5月软考高项冲刺复习攻略,稳过!

    2024-04-01 15:18:01       0 阅读
  5. 树的遍历算法题总结(第二十六天)

    2024-04-01 15:18:01       0 阅读
  6. sqlalchemy expunge的简单使用

    2024-04-01 15:18:01       0 阅读

热门阅读

  1. How to use pandoc in Ubuntu 22.04

    2024-04-01 15:18:01       7 阅读
  2. 缓存的常见问题及其解法

    2024-04-01 15:18:01       5 阅读
  3. 巧克力(蓝桥杯)

    2024-04-01 15:18:01       5 阅读
  4. 本学期学习计划

    2024-04-01 15:18:01       7 阅读
  5. 【Docker笔记06】【容器编排】

    2024-04-01 15:18:01       5 阅读
  6. Qt 中 :deleteLater 总结

    2024-04-01 15:18:01       5 阅读
  7. VLAN配置及原理

    2024-04-01 15:18:01       7 阅读
  8. 网络常见的端口号

    2024-04-01 15:18:01       8 阅读