Java solution, Binary Tree Post Order Traversal


  • 12
    public class Solution {
        int max = 0;
        
        class Result {
            TreeNode node;
            int inc;
            int des;
        }
        
        public int longestConsecutive(TreeNode root) {
            traverse(root);
            return max;
        }
        
        private Result traverse(TreeNode node) {
            if (node == null) return null;
            
            Result left = traverse(node.left);
            Result right = traverse(node.right);
            
            Result curr = new Result();
            curr.node = node;
            curr.inc = 1;
            curr.des = 1;
            
            if (left != null) {
                if (node.val - left.node.val == 1) {
                    curr.inc = Math.max(curr.inc, left.inc + 1);
                }
                else if (node.val - left.node.val == -1) {
                    curr.des = Math.max(curr.des, left.des + 1);
                }
            }
            
            if (right != null) {
                if (node.val - right.node.val == 1) {
                    curr.inc = Math.max(curr.inc, right.inc + 1);
                }
                else if (node.val - right.node.val == -1) {
                    curr.des = Math.max(curr.des, right.des + 1);
                }
            }
            
            max = Math.max(max, curr.inc + curr.des - 1);
            
            return curr;
        }
    }
    

  • 0

    thanks, for sharing~


  • 0

    The answer is good!Thanks.


  • 0

    Really nice solution. Thanks for sharing. Learned a lot from you!


  • 0
    J

    nice solution, but I don't think u need define "node" variable in class Result


  • 0
    F

    Instead of defining a new class object, we can use an array to store the result.

    class Solution {
        int max = 0;
        public int longestConsecutive(TreeNode root) {
            helper(root);
            return max;
        }
        public int[] helper(TreeNode root) {
            if (root == null) {
                return new int[2];
            }
            int[] left = helper(root.left);
            int[] right = helper(root.right);
            int inc = 1, dec = 1;
            if (root.left != null) {
                if (root.val - root.left.val == 1) {
                    inc = left[0] + 1;
                } else if(root.left.val - root.val == 1) {
                    dec = left[1] + 1;
                }
            }
            if (root.right != null) {
                if (root.val - root.right.val == 1) {
                    inc = Math.max(inc, right[0] + 1);
                } else if (root.right.val - root.val == 1) {
                    dec = Math.max(dec, right[1] + 1);
                }
            }
            max = Math.max(max, inc + dec - 1);
            return new int[]{inc, dec};
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.