总结：二叉树的属性-六虎

持续发明，加快成长！这是我参加「日新方案 10 月更文挑战」的第12天，点击查看活动概略

是否对称

给定一个二叉树，查看它是否是镜像对称的。

上图为对称二叉树

上图的二叉树则不是镜像的

思路

判别是否是镜像，需求去判别二叉树的里侧和外侧是否相同。

这就需求去判别根节点下左子树与右子树里侧和外侧是否持平。比较的方法是拿左子树的 “左-右-中” 节点和右子树的“右-左-中”为顺序的节点做比较。

这题用递归的方法解比较便利，递归的思路如下：

由于要比较俩个子树是否是镜像的，所以递归的参数为俩个，分别是左子树节点和右子树节点
中止条件有三个：

左节点为空，右节点不为空，回来 false，左节点不为空，右节点为空，回来 false；
左右节点均不为空，但数值不同，回来 false；
假设左右节点均为空，则回来 true；

假设以上条件均不满足，则再进入递归逻辑

代码完结

public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }
    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }

时刻复杂度：O(N)，其间 N 是树的节点数。对每个节点拜访一次。

空间复杂度：O(H)，其间 H 是树的高度

二叉树的最大深度

给定一个二叉树，找出其最大深度。

思路

二叉树的深度是指根节点到最远叶子节点的最长途径上的节点数。

咱们可以通过递归的方法求解此题：

递归函数的传入的参数为二叉树的根节点，回来值为二叉树的高度；
递归的中止条件为当节点为空节点时，回来高度为 0；
先求出它左子树的高度，然后再求出它右子树的高度，俩高度的最大值+1为二叉树的最大深度。

代码如下：

class solution {
public:
    int getdepth(treenode node) {
        if (node == null) return 0;
        int leftdepth = getdepth(node.left);       // 左
        int rightdepth = getdepth(node.right);     // 右
        int depth = 1 + Math.max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxdepth(treenode root) {
        return getdepth(root);
    }
};

时刻复杂度：O(N)，其间 N 是树的节点数。对每个节点拜访一次。

空间复杂度：O(H)，其间 H 是树的高度

同理，该方法适用于求 N 叉树的最大深度，代码如下：

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
class Solution {
  public int maxDepth(Node root) {
    if (root == null) {
      return 0;
    } else if (root.children.isEmpty()) {
      return 1;  
    } else {
      List<Integer> heights = new LinkedList<>();
      // 循环求出每个子树的高度
      for (Node item : root.children) {
        heights.add(maxDepth(item)); 
      }
      return Collections.max(heights) + 1;
    }
  }
}

时刻复杂度：O(N)，其间 N 是树的节点数。对每个节点拜访一次。

空间复杂度：O(H)，其间 H 是树的高度

二叉树的最小深度

阐明：最小深度是从根节点到最近叶子节点的最短途径上的节点数量。

这里有个误区需求解释一下，是从根节点到最近的叶子节点，假设根节点没有左子树或许右子树，很多人就觉得最小深度为 1，这是不对的。是从根节点到最近叶子节点的最短途径上的节点数量才是最小深度。

可以看出, 求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

代码如下：

class Solution {
    /**
     * 递归法，比较求MaxDepth要复杂点
     * 由于最小深度是从根节点到最近**叶子节点**的最短途径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

时刻复杂度：O(N)，其间 N 是树的节点数。对每个节点拜访一次。

空间复杂度：O(H)，其间 H 是树的高度。

求二叉树有多少个节点

给出一个彻底二叉树，求出该树的节点个数。

此题可用求二叉树的最大深度的方法来求出，代码如下：

class solution {
public:
    int getdepth(treenode node) {
        if (node == null) return 0;
        int leftdepth = getdepth(node.left);       // 左
        int rightdepth = getdepth(node.right);     // 右
        int depth = 1 + leftdepth, rightdepth; // 中
        return depth;
    }
    int maxdepth(treenode root) {
        return getdepth(root);
    }
};

时刻复杂度：O(n)，n 为二叉树节点个数空间复杂度：O(h)，h 为树的高度

平衡二叉树

给定一个二叉树，判别它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树界说为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

思路

既然是要求比较高度，则咱们可以用到后序遍历的方法。

明晰递归函数的参数和回来值，参数为传入的根节点，假设左右子树的回来值 > 1,则咱们回来 -1，标明现已不是平衡二叉树了；
递归的中止条件为遇到了空节点，则 return 0, 标明其时节点为根节点，高度为 0；
单层递归逻辑为，分别求出左右子树的高度，假设差值小于等于 1，则回来其时二叉树的高度，不然回来 -1，标明现已不是二叉树了；

代码如下：

class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1标明现已不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

二叉树的全部路劲

给定一个二叉树，回来全部从根节点到叶子节点的途径。

思路

依据题意要从根节点到叶子节点的途径，所以需求前序遍历。

承认递归的参数和回来值，参数为传入的根节点，记载每条途径的节点值数组path，以及途径结果数组res；
当遇到叶子节点的时分中止，并将途径节点值数组里的数值转换成字符串，然后加入到结果数组；
递归的单层逻辑为，由于是前序遍历：中-左-右，所以先处理中心节点，加入到 path 中，然后再递归处理左子树和右子树，并递归完后回溯；

代码如下：

//解法一
class Solution {
    /**
     * 递归法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();
        traversal(root, paths, res);
        return res;
    }
    private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
        paths.add(root.val);
        // 叶子结点
        if (root.left == null && root.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            res.add(sb.toString());
            return;
        }
        if (root.left != null) {
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) {
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

左叶子之和

核算给定二叉树的全部左叶子之和。

思路

首先要判别这棵二叉树有没有左叶子，就必须要通过节点的父节点来判别其左孩子是不是左叶子，判别代码如下：

 if (root.left != null && root.left.left == null && root.left.right == null) { // 中
            midValue = root.left.val;
        }

用后序遍历找出全部的左叶子节点数值之和，递归方法如下：

递归函数的传参为根节点，回来值为左叶子节点之和；
递归中止条件为 root == null 回来 0；
单层递归逻辑：当遇到左叶子节点的时分，记载数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和；

代码如下：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { // 中
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}

左下角的值

给定一个二叉树，在树的最终一行找到最左边的值。

思路

本题比较简单下手的解题方法可以用层序遍历的方法，找到最终一行的最左边。

可是也可以用递归法来完结，首先可以明晰深度最大的叶子节点一定是最终一行，那怎样找最左边的呢？咱们可以运用前序遍历，优先从左边初步查找。

明晰递归函数的参数和回来值：参数为传入的根节点，以及一个int型变量用来记载最长深度。回来值为 void；
当遇到叶子节点的时分，为中止条件，并初步计算最大深度；
承认单层递归逻辑，当不是叶子节点时，则持续遍历左子树和右子树，并记住要回溯；

代码如下：

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }
    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

路劲总和 1

给定一个二叉树和一个政策和，判别该树中是否存在根节点到叶子节点的途径，这条途径上全部节点值相加等于政策和。

思路

使用递归来回答此题：

承认递归函数的传参和回来值：参数为传入的根节点和计数变量，该计数变量每次递归的时分需求减去其时节点的值，最终遇到叶子节点的时分判别该叶子节点的值是否与它共同，假设共同，则标明找到了该途径。回来值为bool类型；
递归函数的中止条件为：当遇到叶子节点的时分，而且计数变量等于叶子节点的值就回来 true;
单层递归逻辑为：遍历左子树和右子树，并回溯

代码如下：

class solution {
   public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum(root.left, targetsum);
            if (left) {// 现已找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum(root.right, targetsum);
            if (right) {// 现已找到
                return true;
            }
        }
        return false;
    }
}
// 精简后的代码
class solution {
    public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) return false; // 为空退出
        // 叶子节点判别是否契合
        if (root.left == null && root.right == null) return root.val == targetsum;
        // 求两边分支的途径和
        return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
    }
}

途径总和2

给定一个二叉树和一个政策和，找到全部从根节点到叶子节点途径总和等于给定政策和的途径。

思路

解题思路与上一题类似，只是需求记载途径。

代码如下：

class solution {
    public list<list<integer>> pathsum(treenode root, int targetsum) {
        list<list<integer>> res = new arraylist<>();
        if (root == null) return res; // 非空判别
        list<integer> path = new linkedlist<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }
    public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的途径
            if (targetsum - root.val == 0) {
                res.add(new arraylist<>(path));
            }
            return; // 假设和不为 targetsum，回来
        }
        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

我是杰少，假设您觉的我写的不错，那请给我 点赞+谈论+保藏 后再走哦！

往期文章：

运用 Google Breakpad 来助力处理程序溃散
UE4 多人游戏服务器探究
运用虚幻引擎主动化东西完结主动化安置
怎样在 UE4 中制作一扇主动敞开的大门
怎样在 UE4 中用代码去操控人物移动
怎样给 UE4 场景增加游戏人物
UE4：Android 途径开发实践攻略
UE4 开发避坑攻略（持续更新）
新年开工啦，放个小烟花庆祝一下
聊聊与苹果审核员的爱恨情仇(下)
聊聊与苹果审核员的爱恨情仇(上)
一名一般东西人的 2021 | 2021年终总结
二叉树刷题总结：二叉查找树的特色
二叉树总结：二叉树的特色
二叉树总结：二叉树的修改与构造
StoreKit2 有这么香？嗯，我试过了，真香
看完这篇文章，再也不怕面试官问我怎样构造二叉树啦！
那帮做游戏的又想让我们氪金，太坏了！
手把手带你撸一个网易云音乐主页 | 适配篇
手把手带你撸一个网易云音乐主页（三）
手把手带你撸一个网易云音乐主页（二）
手把手带你撸一个网易云音乐主页（一）
代码要写注释吗？写你就输了
Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿
iOS 高雅的处理网络数据，你真的会吗？不如看看这篇
UICollectionView 自界说布局！看这篇就够了

请你喝杯 ☕️ 点赞 + 重视哦～

阅读完记住给我点个赞哦，有有动力
重视大众号— HelloWorld杰少，榜首时刻推送新姿态

最终，发明不易，假设对我们有所帮助，期望我们点赞支持，有什么问题也可以在谈论区里讨论～**

总结：二叉树的属性

是否对称

思路

代码完结

二叉树的最大深度

给定一个二叉树，找出其最大深度。

思路

二叉树的最小深度

求二叉树有多少个节点

平衡二叉树

思路

二叉树的全部路劲

思路

左叶子之和

思路

左下角的值

思路

路劲总和 1

思路

途径总和2

思路

作者信息

推广

总结：二叉树的属性

是否对称

思路

代码完结

二叉树的最大深度

给定一个二叉树，找出其最大深度。

思路

二叉树的最小深度

求二叉树有多少个节点

平衡二叉树

思路

二叉树的全部路劲

思路

左叶子之和

思路

左下角的值

思路

路劲总和 1

思路

途径总和2

思路

相关文章

Android Service 使用详解

如何用 GPT 在 5 分钟内 ”调教“ 出一个专属于你的 ”小黑子“？

yum仓库与NFS共享服务

Android录制视频，UI与Camera分离之UI的抽取

作者信息

推广