遍历思路与子问题思路：详解二叉树的基本操作（二）

2024-05-27 26

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 这篇内容介绍了二叉树的基本操作，包括通过遍历和子问题思路来解决不同的问题。

遍历思路与子问题思路：详解二叉树的基本操作（一）+ https://developer.aliyun.com/article/1520508?spm=a2c6h.13148508.setting.14.61564f0e51sYB8

2、获取叶子节点的个数

遍历思路

用成员变量leafCount标记叶子节点的数目。当左子树与右子树都为null时，这个结点是叶子结点，此时令leafCount++即可。

    //获取叶子节点的个数
    int leafCount;
    public void getLeafNodeCount3(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafCount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }

子问题思路

整棵二叉树的叶子结点个数 = 左子树的叶子结点个数+右子树的叶子结点个数

叶子结点 = 左子树和右子树都为null的结点

掌握这两个结论，可以写出如下代码：

    //获取叶子节点的个数
    public int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
 
        if(root.left == null && root.right == null) {
            return 1;
        }
 
        int left = getLeafNodeCount2(root.left);    //左子树中叶子节点的个数
        int right = getLeafNodeCount2(root.right);    //右子树中叶子节点的个数
 
        return left+right;
    }

或

    //获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
 
        int left = getLeafNodeCount(root.left);
        int right = getLeafNodeCount(root.right);
 
        if(left == 0 && right == 0) {
            return 1;
        }
        return left+right;
    }

从结果上看。两段代码都是正确的。

注意：在一些问题上，子问题的思路分析能够使问题变得更清晰、简便。

3、获取第K层结点的个数

子问题思路

该题的思路比较巧妙。要求第K层的结点个数，一整棵树的第K层 = 它的左子树的第K-1层 = 它的右子树的第K-1层。

一棵树第K层的结点个数 = 左子树第K-1层的结点个数+右子树第K-1层的结点个数。

可以写出如下代码，如果对代码不理解，可以参照前序遍历的图示将递归画图展开。

1.    //获取第k层结点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
 
        int left = getKLevelNodeCount(root.left,k-1);
        int right = getKLevelNodeCount(root.right,k-1);
 
        return left+right;
    }

4、求树的高度

🔗LeetCode-104. 二叉树的最大深度

子问题思路

根据二叉树高度的定义：树的高度或深度是树中结点的最大层次。

一棵二叉树的高度 = 左子树高度与右子树高度的最大值 + 1

由此通项公式，可以写出求二叉树高度的代码：

    //二叉树的高度
    public int getHeight(TreeNode root) {
        if(root == null) {    //空树高度为0 返回0
            return 0;
        }
 
        int left = getHeight(root.left);    //记录左子树的高度
        int right = getHeight(root.right);    //记录右子树的高度
        return Math.max(left,right) + 1;    //返回左子树和右子树的高度的最大值+1，即树的高度
    }

特别注意：若不用变量left和right保存左右子树的高度递归结果，而是直接将递归语句代入求最大值的语句，是不合适的：

虽然在本地IDE中运行，结果不会有错，但在在线OJ中运行，会超出时间限制。因为没有用额外的变量来保存递归结果的话，最终return语句中实际上有四个递归语句，有大量的递归的重复计算，这是非常耗时的。

复杂度分析

时间复杂度：O(N)，每一个结点都要求一次以它为根的树的高度，也就是每一个结点实际都会访问的。

空间复杂度：O(height)，和树的高度有关系。若是单分支的树，则高度为N，空间复杂度即为O(N)，若是满二叉树，则高度为logN，空间复杂度即为O(logN。

5、二叉树的中序遍历

与前面前序遍历的代码相似，只是改变了对元素的操作与递归左右子树的顺序（左根右）。

遍历思路

    //中序遍历 递归 遍历思路
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
    }

子问题思路

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

6、二叉树的后序遍历

与前面前序遍历的代码相似，只是改变了对元素的操作与递归左右子树的顺序（左右根）。

遍历思路

    //后序遍历 递归 遍历思路
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }

子问题思路

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

7、检测值为value的元素是否存在，若存在返回该元素的结点

子问题思路

检测值为value的元素在整棵二叉树是否存在 = 检测左树是否存在该节点（如果存在便结束检测并返回） + 检测右树是否存在该结点（如果存在便结束检测并返回）

该代码的思路类似于前序遍历的思路。每遍历到一个结点，就判断这个结点的值是否与给定的value相匹配。

    //检测值为value的元素是否存在  子问题思路
    public TreeNode find(TreeNode root, int val) {
        if(root == null) {
            return null;
        }
        if(root.value == val) {
            return root;
        }
 
        TreeNode left = find(root.left,val);
        if(left != null) {
            return left;
        }
        TreeNode right = find(root.right,val);
 
        return right;
    }

遍历思路与子问题思路：详解二叉树的基本操作（二）

2、获取叶子节点的个数

遍历思路

子问题思路

3、获取第K层结点的个数

子问题思路

4、求树的高度

子问题思路

子问题思路

6、二叉树的后序遍历

遍历思路

子问题思路

热门文章

最新文章

相关电子书