LC - Tree

Lc 98. Validate Binary Search Tree

Solution 1: Recursion

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidSubTree(root, null, null);
    }

    boolean isValidSubTree(TreeNode node, Integer lower, Integer upper) {
        if (node == null) {
            return true;
        }

        int val = node.val;
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;

        if (!isValidSubTree(node.right, val, upper)) return false;
        if (!isValidSubTree(node.left, lower, val)) return false;
        return true;
    }
}

Solution 2: Inorder Traversal

  • 这样遍历前一个比后一个小才是BST
class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // If next element in inorder traversal
      // is smaller than the previous one
      // that's not BST.
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

LC 105. Construct Binary Tree from Preorder and Inorder Traversal

  • 前序遍历 根节点,左子节点,右子节点
  • 中序遍历 左子节点,根节点,右子节点
  • 没有重复数字
  • 前序遍历的第一个节点是根节点,其在中序遍历当中出现的位置,其之前是左子树,其之后是右子树,可以用这个逻辑来递归进行判断

LC 226. Invert Binary Tree

Solution 1: Recursion

  • 逻辑是每个根节点的左子树是其右子树的翻转,即层层都翻转过了 用递归完成这个逻辑就好
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);

        root.left = right;
        root.right = left;
        return root;
    }
}

Solution 2: Iteration

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        return root;
    }
}

Solution 2: Iterative

LC 543. Diameter of Binary Tree

  • Diameter – length of the longest path between any two nodes in a tre

  • Binary Tree

    public class Solution {
      int max = 0;
    
      public int diameterOfBinaryTree(TreeNode root) {
          maxDepth(root);
          return max;
      }
    
      private int maxDepth(TreeNode root) {
          if (root == null) return 0;
    
          int left = maxDepth(root.left);
          int right = maxDepth(root.right);
    
          max = Math.max(max, left + right);
    
          return Math.max(left, right) + 1;
      }
    }

LC 938. Range Sum of BST

  • 二叉查找树

    • 左子树的值会小于根节点的值
    • 右子树的值都大于根节点的值
  • 二叉查找树当中找区间,一定是需要用到二叉查找树本身的性质的

Solution 1: Brute Force

  • 遍历整个树,对于每个节点,对其进行判断,若值在区间内,则累加到一个全局变量上
class Solution {
    int sum = 0;

    public int rangeSumBST(TreeNode root, int L, int R) {

        addToSum(root, L, R);

        return sum;
    }

    void addToSum(TreeNode node, int L, int R) {
        if (node == null) return;

        if (node.val >= L && node.val <= R) {
            sum += node.val;
        }
        addToSum(node.left, L, R);
        addToSum(node.right, L, R);
    }
}

Solution 2: Leverage on BST

  • 逻辑是如果node.val < L, 那么只有右子树是有可能获取在区间内的值的

    class Solution {
      int ans;
      public int rangeSumBST(TreeNode root, int L, int R) {
          ans = 0;
          dfs(root, L, R);
          return ans;
      }
    
      public void dfs(TreeNode node, int L, int R) {
          if (node != null) {
              if (L <= node.val && node.val <= R)
                  ans += node.val;
              if (L < node.val)
                  dfs(node.left, L, R);
              if (node.val < R)
                  dfs(node.right, L, R);
          }
      }
    }
  • Q: L13 – L16, 为什么不能写成

    • node.val > R
    • node.val < L
  • 因为其实第10行的if判断只是为了加进去ans,没有做其他的逻辑运算的

LC 199: Binary Tree Right Side View

  • 对树的分层操作
    • 使用BFS算法

Solution 1: 使用两个队列

  • 两个队列,一个为当前层,一个为下一层
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        ArrayDeque<TreeNode> currentQueue = new ArrayDeque<>();
        ArrayDeque<TreeNode> nextQueue = new ArrayDeque<>();

        nextQueue.add(root);

        List<Integer> result = new ArrayList<>();

        TreeNode node = null;

        while(!nextQueue.isEmpty()) {

            currentQueue = nextQueue.clone();
            nextQueue.clear();
            while (!currentQueue.isEmpty()) {
                node = currentQueue.poll();

                if (node.left != null) {
                    nextQueue.add(node.left);
                }
                if (node.right != null) {
                    nextQueue.add(node.right);
                }
            }

            if (currentQueue.isEmpty()) {
                result.add(node.val);
            }
        }
        return result;
    }
}

Solution 2: 一个队列 + Sentinel

  • 使用null作为卫兵节点来区分不同层
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList() {
            {offer(root);
            offer(null);}
        };

        TreeNode prev, cur = root;
        List<Integer> result = new ArrayList();

        while (!queue.isEmpty()) {
            prev = cur;
            cur = queue.poll();

            while(cur != null) {
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }

                prev = cur;
                cur = queue.poll();
            }

            result.add(prev.val);

            if (!queue.isEmpty()) queue.offer(null);
        }
        return result;
    }
}

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:LC - Tree

文章字数:1k

本文作者:Leilei Chen

发布时间:2020-11-02, 02:54:24

最后更新:2020-11-05, 12:20:50

原始链接:https://www.llchen60.com/LC-Tree/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏