一棵二叉树,求最大通路长度(即最大左右子树高度之和) 收藏 阅读:39
2020-10-27 14:58:10

题目:一棵二叉树,求最大通路长度(即最大左右子树高度之和)

参考答案

该题与leetcode第104题同题型,定义TreeNode结构如下:

class TreeNode {

   int val;
   TreeNode left;
   TreeNode right;

   public TreeNode(int val) {
       this.val = val;
  }
}

解法一(递归求解)

class Solution {

   public int maxHeight(TreeNode root) {
       if (root == null) {
           return 0;
      }
       return maxChildHeight(root.left) + maxChildHeight(root.right);
  }

   public int maxChildHeight(TreeNode root) {
       if (root == null) {
           return 0;
      }
       int leftHeight = maxChildHeight(root.left);
       int rightHeight = maxChildHeight(root.right);
       return Math.max(leftHeight, rightHeight) + 1;
  }
}

解法二(迭代求解)

public class Solution {

   public int maxHeight(TreeNode root) {
       if (root == null) {
           return 0;
      }
       return maxChildHeight(root.left) + maxChildHeight(root.right);
  }

   public int maxChildHeight(TreeNode root) {
       int height = 0;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.add(root);

       while (!queue.isEmpty()) {
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               height++;
               if (node.left != null) {
                   queue.add(node.left);
              }
               if (node.right != null) {
                   queue.add(node.right);
              }
          }
      }
       return height;
  }
}

读后有收获,请作者喝杯咖啡


全部评论

发表评论