LeetCode 二叉树的遍历【递归入门】

左手的ㄟ右手 2024-03-24 11:14 5阅读 0赞

## LeetCode 二叉树的遍历【递归入门】 ##

> 递归三部曲：
> 
> 1.  确定递归函数参数和返回值
> 2.  确定终止条件
> 3.  确定单层递归的逻辑

伪代码：

//1. 确定递归函数参数和返回值
    本题递归函数无返回值，我们采用全局res存储结果，函数参数传入一个node节点即可
    //2. 确定终止条件
    当node为null时候，表明已经遍历到了某一个子树的末尾，需要return
    //3. 确定单层递归的逻辑
    先取node的值，也就是先取根的值【下面三行代码，res放在前面即为前序；放在中间为中序；放在末尾为后序】
    res.add(node.val);
    getVal(node.left);
    getVal(node.right);

### 1 前序遍历 ：LeetCode-144 ###

![在这里插入图片描述][316c9a276e6e46d5a4b555563ee3d7db.png]

> 前序遍历：根左右，先取根然后左子树，然后右子树

代码：

class Solution {
        
        private List<Integer> res = new ArrayList<>();
        public List<Integer> preorderTraversal(TreeNode root) {
        
            getVal(root);
            return res;
        }
        public void getVal(TreeNode node){
        
            //如果节点为空，直接返回[递归边界]
            if(node == null){
        
                return;
            }
            //根
            res.add(node.val);
            //左
            getVal(node.left);
            //右
            getVal(node.right);
        }
    }

### 2 中序遍历 ###

![在这里插入图片描述][badeb37986df4401bfa974c24101f9cd.png]

> 分析：中序遍历，即取值为左根右

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

### 3 后续遍历 ###

![在这里插入图片描述][ad7ca3e3375046718e9e28046f57eaf4.png]

> 分析：后序遍历，取值为左右根

代码：

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

[316c9a276e6e46d5a4b555563ee3d7db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f529f389a2854ff6890bfc416029a913.png
[badeb37986df4401bfa974c24101f9cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e1a8a63bbe444391999a4d6206eaf74b.png
[ad7ca3e3375046718e9e28046f57eaf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3a309db900bf4cab8acc8006c08390a6.png