트리에 대한 알고리즘 문제 소결

happy: 작은 요약, 후속 계속 보충
부찰·용음은 문제에서 나무의 구조를 언급할 때 다음과 같은 몇 가지 측면에서 고려할 수 있다. 귀속(거대), 창고, 대열이다.예를 들어 다음과 같은 몇 가지 문제.

귀속

두 갈래 나무의 구조가 비교적 고정되어 있기 때문에 한 그루의 나무를 좌우자수로 분해하는 문제를 생각하기 쉽다. 이렇게 하면 하귀환의 사고방식을 사용할 수 있다.귀환하는 동시에 변수의 값(예를 들어 노드, 깊이)을 기록하면 일부 문제를 해결할 수 있다(예를 들어 문제1문제2).여기에는 귀속 방식에 주의할 수 있다. 좌중우, 우중좌 문제다.두 갈래 나무를 검색하는 두 가지 스트리밍 방식은 서로 다른 문제를 해결할 수 있다. 예를 들어 오른쪽 왼쪽을 사용하면 비교적 큰 값을 얻을 수 있다. 예를 들어 제목이다.

제목 0: 두 갈래 나무의 순서 반복 결과 구하기

public class BinaryTreeInorderTraversal {
    /**
     *  ， 
     * @param root  
     * @param list  
     */
    private void solution(TreeNode root, List list) {
        if (root.left != null) {
            solution(root.left, list);
        }
        if (root != null) {
            list.add(root.val);
        }
        if (root.right != null) {
            solution(root.right, list);
        }
    }
​
​
    /**
     *  ， 
     *
     * @param root  
     *              ：
     *             *1： *
     *             *2：pop ， *
     *             *3： *
     *             *4： 3-4*
     */
    private List solution(TreeNode root) {
        List list = new ArrayList<>();
        Stack stack = new Stack<>();
​
        pushAllLeft(root, stack);
​
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            pushAllLeft(node.right, stack);
        }
        return list;
    }
    private void pushAllLeft(TreeNode root, Stack stack) {
        while (null != root) {
            stack.push(root);
            root = root.left;
        }
    }
}

 

제목 1: 잎사귀 노드에 대한 루트 구하기

/**
 * https://leetcode.com/problems/binary-tree-paths/description/
 */
public class BinaryTreePaths {
    List resultList = new ArrayList();
​
    /**
     *    。 。
     * @param root
     * @return  
     */
    public List solution(TreeNode root) {
        if (root == null) {
            return resultList;
        }
        findPaths(root, root.val + "");
        return resultList;
    }
    private void findPaths(TreeNode node, String path) {
        if (node.left == null && node.right == null) {
            resultList.add(path);
        }
        if (node.left != null) {
            findPaths(node.left, path + "->" + node.left.val);
        }
        if (node.right != null) {
            findPaths(node.right, path + "->" + node.right.val);
        }
    }
}
​

제목 2: 교묘한 귀속 1: 역순으로 줄별로 출력 노드의 값

/**
 *  
 *  ：
 * Given binary tree [3,9,20,null,null,15,7],
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * return its bottom-up level order traversal as:
 * [
 * [15,7],
 * [9,20],
 * [3]
 * ]
 * 
 * https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description
 */
public class BinaryTreeLevelOrderTraversal {
    public List> levelOrderBottom(TreeNode root) {
        List> list = new LinkedList>();
​
        levleMaker(list, root, 0);
        return list;
    }
​
    /**
     *    ， ， 
     * @param list   
     * @param root   
     * @param level  
     *               ： ， new、 list
     */
    private void levleMaker(List> list, TreeNode root, int level) {
        if (root == null) return;
        if (list.size() <= level) {
            list.add(new LinkedList());
        }
        levleMaker(list, root.left, level + 1);
        levleMaker(list, root.right, level + 1);
        list.get(list.size() - 1 - level).add(root.val);
    }
}

제목 3: 교묘한 귀속 2: 두 갈래 나무를 검색하면 각 노드에 그보다 큰 노드를 더한다.

  Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST  is changed to the original key plus sum of all keys greater than the original key in BST.
  Example:
  Input: The root of a Binary Search Tree like this:
  5
  /   \
  2     13
  Output: The root of a Greater Tree like this:
  18
  /   \
  20     13
 https://leetcode.com/problems/convert-bst-to-greater-tree/description/
​
public class ConvertBSTtoGreaterTree {
    int sum = 0;
​
    /**
     *  ， 
     *
     * @param root  
     * @return  
     *  ：
     * 1： ， （ ） 
     * （ 。 ， 。）
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null)
            return null;
        convertBST(root.right);
​
        root.val += sum;
        sum = root.val;
​
        convertBST(root.left);
        return root;
    }
}

대열

제목 4: 역순으로 줄에 따라 노드의 값을 출력합니다.같은 제목 2이지만 이 때 대기열 방식을 사용합니다

  /**
     *  
     * @param root
     * @return
     */
    public List> levelOrderBottom2(TreeNode root) {
        List> list = new ArrayList>();
        if (root == null) return list;
​
        Queue queue = new ArrayDeque();
        queue.add(root);
​
        while (!queue.isEmpty()) {
            int levelNum = queue.size();
            List subList = new LinkedList();
            for (int i = 0; i < levelNum; i++) {
                if (queue.peek().left != null) queue.offer(queue.peek().left);
                if (queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            list.add(0, subList);
        }
        return list;
​
    }

창고

제목 5: 컴파일러, 두 갈래 검색 트리의 가장 작은 값을 되돌려줍니다