提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

代码随想录 day 14 144.二叉树的前序遍历 | 145.二叉树的后序遍历 | 94.二叉树的中序遍历

递归 代码
2023-04-18 15:39:10 时间

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

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

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

 1 class Solution {
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> res = new ArrayList<>();
 4         helper(res, root);
 5         return res;
 6     }
 7 
 8     private void helper(List<Integer> res, TreeNode root) {
 9         if (root == null) return;
10         res.add(root.val);
11         helper(res, root.left);
12         helper(res, root.right);
13     }
14 }

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<Integer> preorderTraversal(TreeNode root) {
18         List<Integer> res = new ArrayList<>();
19         Stack<TreeNode> stack = new Stack<>();
20         if (root == null) {
21             return res;
22         }
23         stack.push(root);
24         while (!stack.isEmpty()) {
25             TreeNode cur = stack.pop();
26             res.add(cur.val);
27             if (cur.right != null) {
28                 stack.push(cur.right);
29             }
30             if (cur.left != null) {
31                 stack.push(cur.left);
32             }
33         }
34         return res;
35     }
36 }

145. 二叉树的后序遍历

 

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

 

示例 1：

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

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<Integer> postorderTraversal(TreeNode root) {
18         List<Integer> res = new ArrayList<>();
19         if (root == null) return res;
20         helper(root, res);
21         return res;
22     }
23     private void helper(TreeNode root, List<Integer> res) {
24         if (root == null) return;
25         helper(root.left, res);
26 
27         helper(root.right, res);
28                 res.add(root.val);
29     }
30 }

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<Integer> postorderTraversal(TreeNode root) {
18          List<Integer> res = new ArrayList<>();
19          if (root == null) {
20              return res;
21          }
22          Stack<TreeNode> stack = new Stack<>();
23          stack.push(root);
24          while (!stack.isEmpty()) {
25              TreeNode node = stack.pop();
26              res.add(node.val);
27              if (node.left != null) {
28                  stack.push(node.left);
29              }
30              if (node.right != null) {
31                  stack.push(node.right);
32              }
33          }
34          Collections.reverse(res);
35          return res;
36     }
37 }

94. 二叉树的中序遍历

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

 

示例 1：

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

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<Integer> inorderTraversal(TreeNode root) {
18        List<Integer> res = new ArrayList<>();
19         if (root == null) return res;
20         helper(root, res);
21         return res;
22     }
23         private void helper(TreeNode root, List<Integer> res) {
24         if (root == null) return;
25         helper(root.left, res);
26         res.add(root.val);
27         helper(root.right, res);
28              
29     }
30 }

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

 

相关文章